Na teoria da complexidade dos algoritmos , um sistema de prova interativo é um protocolo formal para a demonstração de teoremas que envolve dois participantes que trocam mensagens. Isso torna possível definir classes de complexidade interessantes, em particular a classe IP que é o modelo usado no teorema PCP que caracteriza a classe NP .
Formalmente, um sistema de prova interativo é uma máquina abstrata que modela uma troca de mensagens entre dois protagonistas: um provador e um verificador ; estes se comunicam para que o provador possa convencer o verificador da veracidade de uma proposição relativa à associação ou não associação de uma sequência de caracteres em uma dada linguagem formal . O provador tem recursos de computação ilimitados, enquanto o verificador tem recursos limitados. Os dois protagonistas interagem pelo tempo que leva para o auditor encontrar uma resposta para o problema e se convencer de que é a certa.
Duas propriedades devem ser satisfeitas:
A classe NP pode ser redefinida usando sistemas de prova interativos. Um problema de decisão (por exemplo, o problema de coloração com três cores) está em NP se houver um sistema de prova interativo, como:
A classe AM é uma classe de complexidade definida usando sistemas de prova interativos, como a classe NP, exceto que o verificador é uma máquina probabilística em tempo polinomial.
A classe IP é a classe definida como AM, ou seja, o verificador é uma máquina probabilística em tempo polinomial, mas há uma série de rodadas de troca de mensagens entre o provador e o verificador.