Referencias Bibliográficas: [,,,Hopcroft and Ullman, 1993]
Temas
- Revisión de las clases P y NP; introducir spacio P y EXP.
- Jerarquía polimonial.
- NP completitud (Teorema de Cook).
- Problemas NP completos clásicos.
- Técnicas de reducción.
Objetivos de Aprendizaje
- Define las clases P y NP (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Evaluar]
- Define la clase P-Space y su relación con la clase EXP [Evaluar]
- Explique el significado de NP-Completo (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Evaluar]
- Muestre ejemplos de problemas clásicos en NP - Completo [Evaluar]
- Pruebe que un problema es NP- Completo reduciendo un problema conocido como NP-Completo [Evaluar]
Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, basado en el modelo de la Computing Curricula de IEEE-CS/ACM