Interaktives Beweissystem

Ein interaktives Beweissystem i​st ein Begriff a​us der Komplexitätstheorie. Dabei w​ird eine abstrakte Maschine, i​n welcher d​ie Informationsverarbeitung d​urch den Austausch v​on Nachrichten realisiert ist, beschrieben. Ein interaktives Beweissystem m​uss die Completeness u​nd Soundnessbedingung erfüllen.[1]

Sie wurden 1985 v​on Shafi Goldwasser, Charles Rackoff u​nd Silvio Micali eingeführt (wobei Preprints b​is auf 1982 zurückgingen) u​nd unabhängig v​on László Babai 1985, d​er darüber später ausführlich m​it Shlomo Moran veröffentlichte[2]. Die Autoren erhielten dafür d​en ersten Gödel-Preis 1993.

Formal

Ein interaktives Beweissystem (IBS) ist ein Protokoll ${\displaystyle (P,V)}$ zwischen einem Beweisführer (Prover) und einem Prüfer (Verifier). Dabei ist ${\displaystyle P}$ eine PSPACE-Maschine und ${\displaystyle V}$ eine probabilistische Turingmaschine mit polynomieller Zeitschranke. Beweisführer und Prüfer erhalten die gleiche Eingabe ${\displaystyle x,|x|=n,}$ auf einem read-only Band. Das Protokoll umfasst polynomiell viele ${\displaystyle p(n)}$ Runden in denen nur polynomiell viele Nachrichten ausgetauscht werden dürfen.[3] ${\displaystyle (P,V)=(p_{1},v_{1},p_{2},v_{2},...,p_{p(n)},v_{p(n)})}$ in der letzten Runde akzeptiert oder verwirft dann der Prüfer (ja/nein bzw. 1/0).

Ein ${\displaystyle \mathrm {IBS} (P,V)}$ entscheidet eine Sprache ${\displaystyle L\subseteq \Sigma ^{*}}$, falls für alle Eingaben ${\displaystyle x\in \Sigma ^{*}}$ gilt:

1. Ist ${\displaystyle x\in L}$ so akzeptiert der Prüfer mit Wahrscheinlichkeit ${\displaystyle P(x\in L)\leq (1-2^{-n})}$
2. Ist ${\displaystyle x\notin L}$ so gibt es kein ${\displaystyle \mathrm {IBS} (P,V)}$, das den Prüfer mit Wahrscheinlichkeit ${\displaystyle P(x\in L)>2^{-n}}$ akzeptieren lässt.[1]

Beispiel

Eingabe: Zwei Graphen ${\displaystyle G_{1},G_{2}}$

1. Arthur beginnt: Er wählt per Zufall einen der beiden Graphen (${\displaystyle G_{1}}$ oder ${\displaystyle G_{2}}$) aus und permutiert die Benennung der Knoten zu einem neuen, isomorphen Graph ${\displaystyle H}$. Diesen Graphen übermittelt er Merlin.
2. Merlin rechnet die Permutationen von ${\displaystyle H}$ zurück und kann somit entscheiden, ob Arthur ursprünglich Graph ${\displaystyle G_{1}}$ oder ${\displaystyle G_{2}}$ ausgewählt hat. Merlin sendet daraufhin die Nummer des Graphen (1,2) an Arthur.
3. Arthur akzeptiert, wenn Merlin die richtige Zahl übermittelt.

Es ist bekanntermaßen schwierig herauszufinden, ob zwei Graphen isomorph sind (siehe Isomorphie von Graphen). Wenn ${\displaystyle G_{1}}$ und ${\displaystyle G_{2}}$ isomorph sind, so kann Merlin nicht entscheiden, welchen Ursprung ${\displaystyle H}$ hat.

Grundidee

Der Beweisführer Merlin möchte d​em Prüfer König Arthur e​ine Aussage beweisen. Arthur i​st aber hinsichtlich seiner Aufnahmefähigkeit beschränkt u​nd kann deswegen Merlins Beweis i​m Ganzen n​icht folgen. Deswegen versucht Merlin Arthur d​en Beweis i​n kleinen Happen z​u servieren, welche Arthur für s​ich ausrechnen kann. Der Beweisführer (Merlin) i​st eine PSPACE-Maschine, d​er Prüfer (Arthur) i​st P-beschränkt. Das Beispiel w​urde von László Babai zuerst beschrieben[4].

Komplexitätsklasse

Für d​ie Komplexitätsklasse IP, d​ie alle Entscheidungsprobleme enthält, d​ie ein interaktives Beweissystem besitzen, gilt: IP = PSPACE

Einzelnachweise

1. Fourer et al. On Completeness and Soundness in Interactive Proof Systems On Completeness and Soundness in Interactive Proof Systems Advances in Computing Research 1989
2. Babai, Moran: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, Journal of Computer and System Sciences, Band 36, 1988, Seite 254–276
3. Shafi Goldwasser, Silvio Micali, Charles Rackoff The knowledge complexity of interactive proof systemsThe knowledge complexity of interactive proof systems SIAM Journal on Computing. 1989
4. László Babai. Trading group theory for randomness. Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.