In der Theorie der Komplexität von Algorithmen ist ein interaktives Beweissystem ein formales Protokoll zur Demonstration von Theoremen, an dem zwei Teilnehmer beteiligt sind, die Nachrichten austauschen. Dies ermöglicht es, interessante Komplexitätsklassen zu definieren, insbesondere die IP- Klasse, die das im PCP-Theorem verwendete Modell ist, das die NP-Klasse charakterisiert .
Formal ist ein interaktives Beweissystem ist eine abstrakte Maschine , welche Modelle ein Austausch von Nachrichten zwischen zwei Protagonisten: ein Prover und ein Verifizierer ; diese kommunizieren, damit der Prüfer den Prüfer von der Richtigkeit einer Aussage über die Zugehörigkeit oder Nicht-Zugehörigkeit einer Zeichenkette in einer bestimmten formalen Sprache überzeugen kann . Der Prüfer verfügt über unbegrenzte Rechenressourcen, während der Prüfer über begrenzte Ressourcen verfügt. Die beiden Protagonisten interagieren so lange, bis der Auditor eine Antwort auf das Problem findet und überzeugt ist, dass es die richtige ist.
Zwei Eigenschaften müssen erfüllt sein:
Die NP-Klasse kann mit interaktiven Beweissystemen neu definiert werden. Ein Entscheidungsproblem (zum Beispiel das Farbproblem mit drei Farben) liegt in NP, wenn es ein interaktives Beweissystem gibt wie:
Die AM-Klasse ist eine Komplexitätsklasse, die unter Verwendung interaktiver Beweissysteme definiert wird, wie die NP-Klasse, außer dass der Verifizierer eine Wahrscheinlichkeitsmaschine in polynomieller Zeit ist.
Die IP-Klasse ist die Klasse, die als AM definiert ist, d. h. dass der Verifizierer eine Wahrscheinlichkeitsmaschine in polynomieller Zeit ist, aber zwischen dem Beweiser und dem Verifizierer eine Reihe von Nachrichtenaustauschrunden stattfindet.