IP (complexidade)

Em Teoria da complexidade computacional, a classe IP (abreviação de Interactive Polynomial Time (Tempo Polinomial Interativo)) é a classe de problemas solúveis em tempo polinomial por um sistema de prova interativa. O conceito de sistemas de provas interativas foi introduzido pela primeira vez por Shafi Goldwasser, Silvio Micali, e Charles Rackoff em 1985. Um sistema de prova interativa consiste em duas máquinas, uma provadora (P) a qual apresenta a prova que uma dada string n é um membro de uma certa linguagem e um verificador (V) o qual verifica se a prova apresentada é correta. Assumindo que a provadora é infinita em armazenamento e computação, enquanto o verificador é uma máquina com tempo polinomial probabilístico com acesso a uma string de bits aleatórios cujo tamanho é polinomial no tamanho n. Essas duas máquinas trocam um número polinomial, p(n), de mensagens e uma vez que a interação é concluída, o verificador deve decidir se n está ou não na linguagem, com apenas 1/3 de chance de erro. (Então, qualquer linguagem em BPP está em IP, sendo assim o verificador poderia simplesmente ignorar o provador e fazer a decisão por conta própria). A linguagem L pertence a IP se existe um V, P para todo Q, w: O Protocolo de Arthur-Merlin, introduzido por Laszlo Babai, é similar em natureza, exceto que o número de rodadas de interação é limitado por uma constante ao invés de um polinômio. Goldwasser et al. mostraram que protocolos de "moeda pública", onde os números randômicos usados por um verificador são providos ao provador juntamente com os desafios, não são menos poderosos do que protocolos de moeda privada. No máximo duas rodadas adicionais de interação são necessárias para replicar o efeito de um protocolo de moeda privada. A inclusão oposta é direta, porque o verificador sempre pode mandar para o provador os resultados dos seus lançamentos de moeda privada, que prova que os dois tipos de protocolos são equivalentes.