Complejidad computacional

Curso de posgrado en ciencias de la computación, segundo semestre de 2012.

Guillaume Hoffmann, FaMAF UNC

Duración: 20 clases (40 horas). Empieza el 21 de agosto.

Horarios/lugar: martes 10h-12h, jueves 10h-13h, aula 24.

Slides

• Teórica 1
• Teórica 2
• Teórica 3
• Teórica 4
• Teórica 5
• Teórica 6: Polynomial Hierarchy (slides 1-85, apuntes de Nabil Mustafa)
• Teórica 7:
  • Randomized Computation (apuntes de Nabil Mustafa)
  • Randomized Computation 2, slides 1-35, Nabil Mustafa
  • UPATH in RL: sección 3.2 (Trapped in a maze), Scott Aaronson
  • Descripción del algoritmo de Miller y Rabin: (leer desde "As I mentioned"), Scott Aaronson
• Teórica 9:
  • Crypto (apuntes de Scott Aaronson y Gus Gutoski)
• Teórica 10:
  • Quantum (apuntes de Scott Aaronson y Gus Gutoski)
  • Quantum Computing (apuntes de Scott Aaronson y Gus Gutoski)
  • Una explicación del algoritmo de Shor por Aaronson
  • The Limits of Quantum Computers, artículo de divulgación de Aaronson (2008)
• Práctica 1
• Práctica 2
• Take Home 1
• Take Home 2
• Todas las slides

Programa

1. P,NP
   • Máquina de Turing
   • P vs NP, NP completitud, reducciones
   • Teorema de Cook-Levin
2. Complejidad espacial
   • PSPACE, NPSPACE. QBF, PSPACE completitud
   • L, NL, PATH, NL completitud, coNL
3. Jerarquía polinomial
4. Computación aleatoria
5. Criptografía
6. Computación cuántica

Bibliografía

• 'Computational Complexity: A Modern Approach', Arora y Barak, 2007 (draft)
• 'Introduction To The Theory Of Computation', Sipser, 1996.
• 'The annotated Turing', Petzold, 2008.

Libros en biblioteca FaMAF

• 'Computational Complexity: A Modern Approach', Arora y Barak, 2007
• 'Introduction To The Theory Of Computation', Sipser (2nd ed)
• 'The P=NP Question and Gödel's Lost Letter', Lipton
• 'Computational complexity', Papadimitriou
• 'Computational complexity : a conceptual perspective', Goldreich

Evaluación

Take home.

Videos

• Una máquina de Turing tangible