Elaborar o estudo de complexidade computacional iniciado em MAC0414, Autômatos, Computabilidade e Complexidade.
Complexidade de tempo e espaço, algoritmos probabilísticos e de aproximação, provas interativas. O Teorema PCP. Tópicos adicionais: Complexidade de circuitos, Criptografia ou Computação quântica.
O Teorema de Cook--Levin. Complexidade de espaço. Teoremas de hierarquia e diagonalização. A hierarquia polinomial. Algoritmos probabilísticos e de aproximação. Provas interativas. O Teorema PCP. Tópicos adicionais: Complexidade de circuitos, Criptografia ou Computação quântica.
Bibliografia Básica: 1. S. Arora e B. Barak, Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009. xxiv + 579pp. ISBN: 978-0-521-42426-4 2. M. Sipser, Introduction to the Theory of Computation. Cengage Learning, Boston, MA. 3rd edition, 2013. xxii + 458pp. 3. C. H. Papadimitriou, Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. xvi + 523pp. ISBN: 0-201-53082-1 4. H. R. Lewis, C. H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.