De PH a IP : un curso en complejidad computacional

Abstract

En este trabajo estudiamos algunas de las clases más importantes de la teoría de Complejidad Computacional. Nos basamos en el programa que propone el libro Computational Complexity a modern approach, del cual vemos la segunda mitad de la primera parte del programa (excluyendo Criptografía, Computación Cuántica y el Teorema PCP). En particular, estudiamos la clase de la Jerarquía Polinomial (PH), la clase de Circuitos Booleanos (P /poly ), la Computación Randomizada (BPP) y los Protocolos Interactivos (IP). Además vemos las principales técnicas de la teoría para obtener resultados las cuales son Diagonalización, Lower bounds y Arithmetization. Y estudiamos también sus respectivas limitaciones: Relativización, Natural proofs y Algebrization.

In this work we study some of the most important classes of the Computational Complexity Theory. We base on the program proposed by the book Computational Complexity a modern approach, of which we see the second half of the first part of the program (excluding Cryptography, Quantum Computing and the PCP Theorem). In particular, we study the class of the Polynomial Hierarchy (PH), the class of Boolean Circuits (P /poly ), the Randomized Computing (BPP) and the Interactive Protocols (IP). In addition we see the main techniques of the theory to obtain results which are Diagonalization, Lower bounds and Arithmetization. And we also study their respective limitations: Relativization, Natural proofs and Algebrization.