Programa

Demonstrações, Computabilidade, Complexidade

Mestrado Bolonha em Matemática

Programa

• A invenção do computador: as máquinas de Turing. • Implementação de vários algoritmos em máquinas de Turing. • Outros modelos de computação: máquinas de acesso aleatório, Baby Python, funções recursivas de GödelHerbrand. Provas de equivalência/simulação. • Máquinas de Turing universais e programas. A tese de Church-Turing. • Problemas insolúveis. O problema da paragem e muitos outros. • Lógica de primeira ordem e o primeiro teorema da incompletude de Gödel (em apenas uma semana!). • Problemas recursivamente enumeráveis e um problema que não é recursivamente enumerável. A hierarquia aritmética. • Complexidade computacional: medição de tempo e espaço, o problema P vs PSPACE. Teoremas da hierarquia. • Máquinas de Turing não determinísticas: o problema P vs NP. • O teorema de Levin-Cook. NP-completude de vários problemas. Decisão vs Pesquisa. A hierarquia polinomial. • De volta ao espaço: o teorema de Savitch. PSPACE-completude. L vs NL. • Algoritmos aleatorizados: P vs BPP e mais. • A complexidade das provas: provas interativas, MA, AM, etc., até IP = PSPACE.