Programa

Complexidade Computacional

Mestrado Bolonha em Engenharia Informática

Mestrado Bolonha em Ciência de Dados

Mestrado Bolonha em Segurança Informática

Mestrado Bolonha em Matemática

Mestrado Bolonha em Bioinformática e Biologia Computacional

Programa

Parte 1 - Classes de Complexidade e Diagonalização * A invenção do computador: máquinas de Turing e o problema da paragem * Medidas de complexidade e Máquinas de Acesso Aleatório * Teoremas de hierarquia * A carta perdida de Gödel, reduções, teorema de Cook-Levin, P vs NP * Complexidade de espaço: L vs NL vs P vs PSPACE * A barreira da relativização Parte 2 - A abordagem combinatória * Modelos combinatórios: Circuitos Booleanos, limites inferiores, redução de profundidade * Computação randomizada: ZPP, RP, BPP, desrandomização, dureza vs aleatoriedade * Algoritmos e limites inferiores para circuitos de profundidade constante * A fronteira nos limites inferiores de circuitos: Circuitos de profundidade constante com portas modulares * Complexidade da comunicação e o teorema de Karchmer-Wigderson * Alguns limites inferiores em complexidade da comunicação * A barreira das provas naturais Parte 3 - Outros tópicos (apresentações dos alunos)