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 , 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).