- Interaktives Beweissystem
-
Ein interaktives Beweissystem ist ein Begriff aus der Komplexitätstheorie. Dabei wird eine abstrakte Maschine, in welcher die Informationsverarbeitung durch den Austausch von Nachrichten realisiert ist, beschrieben. Ein interaktives Beweissystem muss die Completeness und Soundnessbedingung erfüllen. [1]
Sie wurden 1985 von Shafi Goldwasser, Charles Rackoff und Silvio Micali eingeführt (wobei Preprints bis auf 1982 zurückgingen) und unabhängig von Laszlo Babai 1985, der darüber später ausführlich mit Shlomo Moran veröffentlichte[2]. Die Autoren erhielten dafür den ersten Gödel-Preis 1993.
Inhaltsverzeichnis
Formal
Ein interaktives Beweissystem (IBS) ist Protokoll (P,V) zwischen einem Beweisführer (Prover) und einem Prüfer (Verifier). Dabei ist P eine PSPACE-Maschine und V eine randomisierte Turingmaschine mit polynomieller Zeitschranke. Beweisführer und Prüfer erhalten die gleiche Eingabe x, | x | = n, auf einem read-only Band. Das Protokoll umfasst polynomiell viele p(n) Runden in denen nur polynomiell viele Nachrichten ausgetauscht werden dürfen.[3] (P,V) = (p1,v1,p2,v2,...,pp(n),vp(n)) in der letzten Runde akzeptiert oder verwirft dann der Prüfer (ja/nein bzw. 1/0).
Ein IBS(P,V) entscheidet eine Sprache
, falls für alle Eingaben
gilt:
- Ist
so akzeptiert der Prüfer mit Wahrscheinlichkeit
- Ist
so gibt es kein IBS(P,V), dass den Prüfer mit Wahrscheinlichkeit
2^{-n}" border="0"> akzeptieren lässt. [4]
Beispiel
Eingabe: Zwei Graphen G1,G2
- Arthur beginnt: Er wählt per Zufall einen der beiden Graphen (G1 oder G2) aus und permutiert die Benennung der Knoten zu einem neuen, isomorphen Graph H. Diesen Graphen übermittelt er Merlin.
- Merlin rechnet die Permutationen von H zurück und kann somit entscheiden, ob Arthur ursprünglich Graph G1 oder G2 ausgewählt hat. Merlin sendet daraufhin die Nummer des Graphen (1,2) an Arthur.
- Arthur akzeptiert, wenn Merlin die richtige Zahl übermittelt.
Es ist bekanntermaßen schwierig herauszufinden, ob zwei Graphen isomorph sind (siehe Isomorphie von Graphen). Wenn G1 und G2 isomorph sind, so kann Merlin nicht entscheiden, welchen Ursprung H hat.
Grundidee
Der Beweisführer Merlin möchte dem Prüfer König Arthur eine Aussage beweisen. Arthur ist aber hinsichtlich seiner Aufnahmefähigkeit beschränkt und kann deswegen Merlins Beweis im Ganzen nicht folgen. Deswegen versucht Merlin Arthur den Beweis in kleinen Happen zu servieren, welche Arthur für sich ausrechnen kann. Der Beweisführer (Merlin) ist eine PSPACE-Maschine, der Prüfer (Arthur) ist P-beschränkt. Das Beispiel wurde von László Babai zuerst beschrieben[5].
Komplexitätsklasse
Für die Komplexitätsklasse IP, die alle Entscheidungsprobleme enthält, die ein interaktives Beweissystem besitzen, gilt: IP = PSPACE
Einzelnachweise
- ↑ Fourer et al. On Completeness and Soundness in Interactive Proof Systems On Completeness and Soundness in Interactive Proof Systems Advances in Computing Research 1989
- ↑ 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
- ↑ Shafi Goldwasser, Silvio Micali, Charles Rackoff The knowledge complexity of interactive proof systemsThe knowledge complexity of interactive proof systems SIAM Journal on Computing. 1989
- ↑ Fourer et al. On Completeness and Soundness in Interactive Proof Systems On Completeness and Soundness in Interactive Proof Systems Advances in Computing Research 1989
- ↑ László Babai. Trading group theory for randomness. Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.
- Ist
Wikimedia Foundation.