Sistema de prova interativa

Na teoria da complexidade, um sistema de prova interativa é uma máquina abstrata que formula computação como a troca de mensagens entre duas partes. As duas partes, o verificador e o provador, interagem através da troca de mensagens, a fim de verificar se uma determinada cadeia pertence a uma linguagem ou não. O provador é muito poderoso e possui recursos computacionais ilimitados, mas não é confiável, enquanto que o verificador tem poder computacional limitado. Mensagens são enviadas entre o verificador e o provador até que o verificador tenha uma resposta ao problema e tenha "convencido" ele mesmo de que está correto.

Todas as provas de sistema interativo tem dois requisitos:

• Completude: se a afirmação é verdadeira, o verificador (isto é, que segue o protocolo adequadamente) irá ser convencido deste fato por um provador honesto.
• Corretude: se uma afirmação é falsa, nenhum provador, mesmo se ele não segue o protocolo, conseguirá convencer o verificador honesto de que isso é verdade, exceto com pequena probabilidade.

Assume-se que o verificador é sempre honesto.

A natureza específica do sistema, e assim a classe de complexidade das linguagens que podem ser reconhecidas, depende de que tipo de limites são colocados no verificador, bem como quais habilidades são dadas — por exemplo, muitos sistemas de provas interativas dependem criticamente da habilidade do verificador de fazer escolhas aleatórias. Isso também depende da natureza da mensagem trocada — quantas e quais eles podem conter. Sistemas interativos de prova foram encontrados para ter algumas implicações importantes para complexidade de classes tradicional definida usando somente máquinas. As principais classes de complexidade que descrevem sistemas de provas interativos são AM e IP.