Todos são bem-vindos!!
Seminário de Algoritmos e Combinatória
Título: Sistemas interativos de prova
Palestrante: Carlos Henrique Cardonha
Local: sala 241 do bloco A
Data: terça, 27 de setembro, das 13:00 às 14:00
Resumo:
Em meados da década de 80, surgiu a proposta de uma nova
classe de complexidade computacional definida em função dos
chamados sistemas interativos de prova. Tais sistemas são
uma generalização do sistema de prova implícito na definição
da classe NP. Neste seminário, apresentamos os sistemas
interativos de prova, as classes de complexidade IP e AM,
definidas a partir deles, e apresentamos o principal
resultado envolvendo estas classes: que IP = AM = PSPACE.
Forum