Complejidad computacional

Curso de posgrado segundo semestre de 2014.

FFHA, Universidad Nacional de San Juan

Guillaume Hoffmann

Horarios/lugar:

Programa y apuntes

1. Modelos de cálculo, máquinas de Turing
   • circuitos booleanos
   • automatas
   • Máquina de Turing
   • MT universal
   • problema de la detención
   • slides
   • slides en una sóla página
   • ejercicios
2. 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
   • slides en una sóla página
   • Polynomial Hierarchy (slides 1-85, apuntes de Nabil Mustafa)
   • ejercicios
3. Complejidad espacial
   • PSPACE, NPSPACE.
   • QBF, PSPACE completitud
   • L, NL
   • PATH, NL completitud
   • coNL
   • slides
   • slides en una sóla página
   • ejercicios
4. Computación aleatoria
   • aleatoriedad en el mundo real
   • reducción de la probabilidad de error
   • RP, coRP, BPP, ZPP
   • Primes
   • slides
   • slides en una sóla página
   • Randomized Computation, Nabil Mustafa (fuente 1, 2)
   • ejercicios
5. Criptografía
   • slides
   • slides en una sóla página

Slides del 2012

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

Videos

• Una máquina de Turing tangible
  
• Otra máquina de Turing hecha con Legos