Sistema de demostració interactiu

En teoria de la complexitat, un sistema de demostració interactiu és una màquina abstracta que modela la computació com un intercanvi de missatges entre dues parts. Aquestes parts, el Verificador i el Provador, es comuniquen intercanviant-se missatges per determinar si una cadena donada pertany a un llenguatge o no. El provador te tota la potència de càlcul que calgui però no se'n pot confiar, i el verificador té una potència de càlcul fitada. S'intercanvien missatges entre l'un i l'altre fins que el verificador creu que la resposta és correcta.

Tots els sistemes de demostració interactius tenen dos requeriments:

• Complets: si l'entrada se certa, el verificador honest (aquell que segueix correctament el protocol) pot ser convençut per un verificador no confiable.
• Solidesa: si l'entrada és falsa, cap provador, inclús si no segueix el protocol, pot convèncer el verificador que és cert, excepte amb una petita probabilitat.

S'assumeix que el verificador sempre és honest.

La natura específica del sistema, i per tant de la classe de complexitat que defineix depèn de quines restriccions es posen al verificador i de quines habilitats se li donen. Les classes de complexitat més importants amb aquest tipus d'arquitectura són les classes AM i IP.

NP

La classe NP es pot veure com un cas molt simple de sistema de demostració interactiu. En aquest sistema, el verificador és una màquina determinista en temps polinòmic (una màquina de la classe P). El protocol és:

• El provador mira l'entrada i computa la solució usant la seva potència il·limitada i retorna un certificat de mida polinòmica
• El verificador verifica que el certificat és vàlid en un temps polinòmic i determinista. Si és vàlid, accepta, si no, el rebutja.

El cas que un certificat sigui vàlid, el provador sempre es capaç de fer que el verificador accepti donant-li el certificat. En el cas que no hi hagi cap certificat vàlid, l'entrada no és del llenguatge i cap provador pot convèncer el verificador, perquè qualsevol certificat serà rebutjat.