Programa

Computabilidade e Complexidade

Diploma de Estudos Avançados em Segurança de Informação

Programa

Computação com recursos limitados no espaço e no tempo. Classes de complexidade notáveis. Problemas notáveis em complexidade estrutural. Conjuntos NP-completos e PSPACE-completos. Teorias de redução em tempo polinomial: redução de muitos para um e redução segundo Turing. Classes de complexidade não uniforme: teorias de conselhos polinomiais e de conselhos logarítmicos. Circuitos booleanos. Máquinas de Turing probabilísticas. Classes probabilísticas centrais: PP, BPP e ZPP. A hierarquia (de tempo) polinomial: definição, caracterização e consequências. Relação da hierarquia polinomial com classes probabilísticas.