Programa

Computabilidade e Complexidade

Mestrado Bolonha em Engenharia e Ciência de Dados

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

Mestrado Bolonha em Segurança de Informação e Direito no Ciberespaço

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

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

Programa

Computação com recursos limitados no espaço e no tempo. Relações estruturais entre classes de complexidade. Reduções com recursos limitados de muitos para um (tempo polinomial, espaço logarítmico) e de Turing. Conjuntos NP-completos, PSPACE-completos e NL-completos. Conjuntos P-completos. Alternação. Classes de complexidade para a alternação. A hierarquia polinomial. Classes de complexidade não uniforme e circuitos booleanos. Máquinas de Turing probabilísticas. Classes PP, BPP, R e ZPP. Relativizações negativas e positivas. Isomorfismo e NP-completude: cilindros e conjuntos esparsos completos. Máquinas de Turing interativas. Jogos Artur contra Merlin e sistemas de prova.