Da lógica à complexidade

Resumo: Formulação rigorosa do problema P=NP? Sentenças Pi-zero-um e Pi-zero-dois. Sentenças indecidíveis Pi-zero-um são verdadeiras no `modelo standard.' Consequência: na formulacão rigorosa usual, se P=NP é independente dos axiomas da aritmética, então P<NP é verdadeiro. (Se der tempo: omega-inconsistência e modelos não-standard para P=NP.) Teorema de Kreisel. Vista d'olhos sobre a prova da consistência de Gentzen. Da prova de Gentzen à hierarquia das funções recursivas provadamente totais na aritmética. Do teorema de Kreisel ao problema P=NP? e a consistência de P=NP com a aritmética formalizada.