Las partes son el verificador y el demostrador, quienes interactúan por intercambio de mensajes para demostrar la pertenencia o no de una palabra dada a un lenguaje.El verificador realiza preguntas al demostrador un número limitado de veces para determinar si la palabra dada pertenece o no al lenguaje.Se ha demostrado que el conjunto de todos los lenguajes reconocibles por interacción (llamado clase de complejidad IP) es equivalente al conjunto de todos los lenguajes reconocibles por una máquina de Turing usando espacio polinómico.Usualmente, en un sistema de demostración interactivo, el verificador puede almacenar conocimiento previo.Más adelante Goldwasser y Sipser demostraron que el conjunto de lenguajes que tienen pruebas interactivas con conocimiento privado también tienen pruebas interactivas con conocimiento público.
Representación general de un protocolo de prueba interactivo.
