4.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.