4.29.4.5 AL/Clases de Complejidad P y NP. (4 horas) [Nivel Bloom 5]

Referencias Bibliográficas: [Kleinberg and Tardos, 2005,Dasgupta et al., 2006,Cormen et al., 2009]

Tópicos

1. Definición de las clases P y NP.
2. NP-completitud (El teorema de Cook).
3. Problemas NP-completos estándares.
4. Técnicas de reducción.

Objetivos

1. Definir las clases P y NP.
2. Explicar el significado de la NP-Completitud.
3. Probar que un problema es NP-completo reducciendo un problema NP-Completo clásico conocido a éste.