Apuntes de (Introducción a la) Complejidad Computacional
2da versión con ilustraciones (Formato Postcript, 2.7 MB comprimido) ,
2da versión sin ilustraciones (Formato DVI, 171 KB comprimido) .
Marzo 2002: este es un adelanto tentativo de la segunda versión de la traducción modificada y con adiciones de los Apuntes de Complejidad Computacional (95 pág., formato postcript comprimido 205K) de P. Gacs y L. Lovasz, Computational Complexity. En la traducción participaron P. Barcelo, C. Bastarrica, R. Cabello, P. Castañeda, A. Cortes, C. Tondreau, R. Rojas. En esta 2da. versión participó activamente Pedro Ortega con sugerencias y correcciones. Todas las ilustraciones son de él. Como siempre, errores y modificaciones son de la responsabilidad de C. Gutiérrez.

Versiones (casi) definitivas (apuntes para el segundo semestre 2002):

• Capítulo 1: Modelos de Computación
• Capítulo 2: Computación con recursos limitados

• Capítulo N: Jerarquía Polinomial (escrita por C. Orellana y M. Vines)

Artículos y sitios de interés:

• PRIMES is in P , M. Agrawal, N. Kayal, N. Saxena, 6 Agosto 2002
• PRIMALIDAD: De Eratóstenes a Agrawal-Kayal-Saxena C. Gutiérrez, Nov. 2002.
• The Complexity Zoo, Zookeeper: Scott Aaronson. Más de 200 clases de complejidad descritas con referencias.
• Complexity Theory Survey by Oded Goldreich (14 pp.)
• The P versus NP Problem, Stephen Cook. Preparado para los Millennium Prize Problems (revisado Nov. 2000)
• A Survey of Models of Parallel Computation , D. K. G. C. Campbell, 1997.
• Average-Case Computational Complexity Theory Forum
• The Implicit Computational Complexity of Imperative Programming Languages, Lars Kristiansen, 2001.
• An introduction to quantum complexity theory , Richard Cleve, 2000.
• Computational Complexity of Games and Puzzles , D. Eppstein
• Descriptive Complexity , Neil Immerman
• The Parameterized Complexity of Database Queries, Martin Grohe, 1999.
• On the Complexity of Database Queries, Ch. Papadimitriou, M. Yannakakis, 1997.
• The complexity of relational query languages, M. Vardi, 1982.
• Rod Downey' papers on Parameterized Complexity
• Kolmogorov Complexity and Solomonoff Induction, página mantenida por Marcus Hutter
• Handboook of Applied Criptography, by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (gratis!!)

Otros apuntes online de cursos de Complejidad Computacional

• Intro to Computational Complexity , Ch. Rackoff, 2000.

Otros apuntes de temas relacionados:

• Fundamentals of Computing , Leonid A. Levin

Charlas sobre temas específicos (de alumnos del curso Complejidad 2002)
Ventaja: acercamiento intuitivo a los temas; Desventaja: pequeños errores ;)

• Complejidad Promedio , Rodrigo Paredes (U. Chile)
• Una presentación del algoritmo AKS "Primes is in P" , Cristian Ruz (P. U. Católica)
• Otra presentación de "Primes is in P" Eduardo Maureira (U. Chile)
• Complejidad Parametrizada de Consultas a Bases de Datos , Mauricio Vines (P. U. Católica)
• Introducción a la Complejidad de Kolmogorov , Pedro Ortega (U. Chile)
• Criptografía , Horacio González (P. U. Católica).