4.21.5.3 Teoría de la Complejidad (20 horas)

Resultados de la carrera Outcomes:

Temas

1. Revisión de las clases P y NP; introducir spacio P y EXP.
2. Jerarquía polimonial.
3. NP completitud (Teorema de Cook).
4. Problemas NP completos clásicos.
5. Técnicas de reducción.

Objetivos de Aprendizaje (Learning Outcomes)

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

Bibliografía: [Sipser, 2012,Kelley, 1995,Hopcroft and Ullman, 2008]