Apontamentos
- Máquinas de Turing e Introdução à Computabilidade, Nelma Moreira, DCC-FCUP
- Classes de Complexidade, Nelma Moreira, DCC-FCUP
Bibliografia
J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages and Computation, 1979
Cap. 7, 8, 12,13
C. Papadimitriou, Computational Complexity , 1994
Cap 1,2, 7-11,13-20
M. Sipser, Introduction to the Theory of Computation, 2005
M. Garey /David. Johnson. Computers and intractability. A Guide to the theory of NP-Completeness, 1979.
Diversos
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
Interview with Stephen Cook
Karp’s homepage and list
P vs NP
Complexity Garden:wiki de problemas e a sua relação com as classes de complexidade
Cook Theorem e Cook’s papers
Interview with Stephen Cook
Karp’s homepage and list
P vs NP
Outras ligações
- Complexity Theory, Dieter van Melkebeek
