Apontamentos


Bibliografia
Stacks Image 2400
Sanjeev Arora and Boaz Barak;Complexity Theory: A Modern Approach
Stacks Image 2476
J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages and Computation, 1979
Cap. 7, 8, 12,13
Stacks Image 2513
C. Papadimitriou, Computational Complexity , 1994
Cap 1,2, 7-11,13-20
Stacks Image 2985
M. Sipser, Introduction to the Theory of Computation, 2005
Stacks Image 2978
M. Garey /David. Johnson. Computers and intractability. A Guide to the theory of NP-Completeness, 1979.
Diversos
Stacks Image 2610
Complexity Zoo: wiki de classes de complexidade

Complexity Garden:wiki de problemas e a sua relação com as classes de complexidade

Cook Theorem e Cook’s papers

Karp’s homepage and list

P vs NP
Stacks Image 3211
PCP THEOREM

Course