5.20.4.8 Teoría de la Complejidad Computacional (6 horas) [Habilidades ]

Referencias Bibliográficas: [Sipser, 2012,Cormen et al., 2022]

Temas

1. Tractabilidad e intractabilidad:
   1. Clases de Complejidad P, NP y NP-Completo
   2. Problemas NP-Completos (por ejemplo, SAT, Mochila, TSP)
   3. Reducciones
2. 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)

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]