2.3.6 AL/Clases de Complejidad P y NP.
Tópicos
- Definición de las clases P y NP.
- NP-completitud (El teorema de Cook).
- Problemas NP-completos estándares.
- Técnicas de reducción.
Objetivos
- Definir las clases P y NP.
- Explicar el significado de la NP-Completitud.
- Probar que un problema es NP-completo reducciendo un problema NP-Completo clásico conocido a éste.
Generado por Ernesto Cuadros-Vargas , Universidad Católica San Pablo, Arequipa-Perú
basado en el modelo de la Sociedad Peruana de Computación y en la Computing Curricula de IEEE-CS/ACM
