Programa

Computabilidade e Complexidade

Mestrado Bolonha em Matemática Aplicada e Computação

Mestrado Bolonha em Engenharia Informática e de Computadores - Alameda

Programa

Modelos de computação. Computabilidade. Computação com recursos limitados no espaço e no tempo. Postulados de Church-Turing e invariância. Classes de complexidade notáveis. Teorias de redução em tempo e espaço limitados. Conjuntos P-completos, NP-completos e PSPACE-completos. Aplicações à Criptografia. Circuitos booleanos. Classes probabilísticas. Diagonalização uniforme. A hierarquia polinomial. Relativização de relações estruturais entre classes de complexidade.