Computabilidade e Tratabilidade via Lógica
Parte 1) Teoria das funções recursivas, Lógica de primeria Ordem, Teoremas da Incompletude de Goedel, Máquinas de Turing, Indecidibilidade da Lógica de Primeira Ordem.
Parte 2) (In)Tratabilidade. Máquinas de Turing de Tempo Polinomial. A Classe P, NP. NP-completude. Teorema de Cook-Levin. P-ESPAÇO-completude.
- Professor: Marcelo Finger