2.2.8 AL/Teoría de la Complejidad Computacional

Temas:
Core

• Tractabilidad e intractabilidad:
  1. Clases de Complejidad P, NP y NP-Completo
  2. Problemas NP-Completos (por ejemplo, SAT, Mochila, TSP)
  3. Reducciones
• Modelos de complejidad basados en Máquinas de Turing:
  1. Complejidad de tiempo:
     1. Clases P, NP, NP-C y EXP
     2. Teorema de Cook-Levin
  2. Complejidad de espacio:
     1. NSpace y PSpace
     2. Teorema de Savitch

Aprendizaje esperado (Learning Outcomes):
Core:

1. Explicar la importancia de la NP-Completitud [Explicar]
2. Explicar cómo NP-Duro es una cota inferior y NP es una cota superior para la NP-Completitud [Explicar]
3. Explicar ejemplos de problemas NP-completos [Explicar]
4. Explicar el Teorema de Cook-Levin y la NP-Completitud de SAT [Explicar]
5. Explicar las clases P y NP [Explicar]
6. Demostrar que un problema es NP-Completo reduciendo un problema NP-C clásico conocido a él (por ejemplo, 3SAT y Clique) [Crear]
7. Explicar la clase P-espacio y su relación con la clase EXP [Explicar]