2.1.5 AL/Complejidad Computacional Avanzada

Temas:
Electivo

• 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 (Learning Outcomes):
Elective:

1. Define las clases P y NP (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Familiarizarse]
2. Define la clase P-Space y su relación con la clase EXP [Familiarizarse]
3. Explique el significado de NP-Completo (También aparece en AL / Automata Básico, Computalidad y Complejidad) [Familiarizarse]
4. Muestre ejemplos de problemas clásicos en NP - Completo [Familiarizarse]
5. Pruebe que un problema es NP- Completo reduciendo un problema conocido como NP-Completo [Usar]