Complexidade Computacional

Ementa

Classes básicas de complexidade de tempo e espaço. A hierarquia polinomial. Complexidade e computação aleatorizada. Classes de computação quântica. O Teorema PCP.

Bibliografia

1. S. Arora; and B. Barak. Computational Complexity: A Modern Approach. Princeton, 2009.

2. C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.

3. S. P. Vadhan. A Study of Statistical Zero-knowledge Proofs. PhD thesis, Massachusetts Institute of  Technology, Cambridge, MA, USA, 1999.