% Complejidad computacional
Curso de posgrado segundo semestre de 2014.
FFHA, Universidad Nacional de San Juan
Docente: Guillaume Hoffmann
Programa y apuntes
- Modelos de cálculo, máquinas de Turing
- circuitos booleanos
- automatas
- Máquina de Turing
- MT universal
- problema de la detención
- slides
- ejercicios
- Clases de complejidad
- clases en tiempo: P, EXPTIME, ejemplos
- en espacio: PSPACE, EXPSPACE, LOGSPACE
- grafos de configuración
- relación entre clases
- space/time hierarchy theorems
- speedup (por una constante)
- reducciones, hardness, completeness
- definiciones de NP
- NP completitud, problema SAT
- Teorema de Cook-Levin
- slides
- Polynomial Hierarchy (slides 1-85, apuntes de Nabil Mustafa)
- ejercicios
- Complejidad espacial
- PSPACE, NPSPACE.
- QBF, PSPACE completitud
- L, NL
- PATH, NL completitud
- coNL
- slides
- ejercicios
- Computación aleatoria
- aleatoriedad en el mundo real
- reducción de la probabilidad de error
- RP, coRP, BPP, ZPP
- Primes
- slides
- Randomized Computation, Nabil Mustafa (fuente 1, 2)
- ejercicios
- Criptografía
- Prácticos para resolver en casa
Bibliografía
- ‘The annotated Turing’, Petzold, 2008.
- ‘Introduction To The Theory Of Computation’, Sipser, 1996.
- ‘Computational Complexity: A Modern Approach’, Arora y Barak, 2007 (draft)
Más bibliografía
- ‘Computational complexity’, Papadimitriou
- ‘The P=NP Question and Gödel’s Lost Letter’, Lipton
- ‘Computational complexity : a conceptual perspective’, Goldreich draft