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

Referencias Bibliográficas: [Kelley, 1995,Hopcroft and Ullman, 1993]

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.



Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, Universidad Católica San Pablo, Arequipa-Peru
basado en el modelo de la Computing Curricula de IEEE-CS/ACM