16
Complejidad

Examen final

Complejidad

Semana 16 — Examen final

Esta semana no hay clases regulares ni laboratorio.

Temas del examen

Todo el curso, con énfasis en las semanas 9 a 15:

  • Lenguajes decidibles y reconocibles. Diagonalización y el problema de la parada.
  • Reducciones, reducción por función y teorema de Rice. PCP y los problemas indecidibles sobre gramáticas.
  • Teorema de recursión, incompletitud y complejidad de Kolmogorov.
  • Tiempo: P, NP con verificadores y con máquinas no deterministas, coNP.
  • Teorema de Cook-Levin y NP-completitud.
  • Espacio: Savitch, PSPACE, TQBF y juegos, L y NL.
  • Teoremas de jerarquía y BPP.
  • De las semanas 1 a 7: saber ubicar un lenguaje en el mapa completo y justificarlo.

Cómo prepararse

  1. Revisar el formato y los consejos de exams/README.md.
  2. Rehacer las preguntas de repaso de las guías 9 a 15.
  3. Dibujar de memoria el mapa de clases, con un lenguaje que separe cada nivel y la técnica que lo demuestra.
  4. Para cada reducción de los apuntes, escribir primero de qué problema a cuál va y por qué en esa dirección.
  5. Rehacer las prácticas 3 y 4 sin mirar la solución.