EDITAR el 2011/02/08: Después de encontrar y leer algunas referencias, decidí separar la pregunta original en dos. Aquí está la parte relativa a UP vs NP, para la parte de clases sintácticas y semánticas, consulte Beneficios para clases sintácticas y semánticas . (el tiempo polinómico...