imported>Siegbert v2: QS: tote Links repariert / ref-Tag nach Satzzeichen

2025-11-06T06:15:56Z

QS: tote Links repariert / ref-Tag nach Satzzeichen

Neue Seite

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 [[Vollständigkeit (Logik)|Completeness]] und [[Korrektheit (Logik)|Soundnessbedingung]] erfüllen.<ref name="Fourer">{{Internetquelle |autor=Fourer et al. |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.9412&rep=rep1&type=pdf |titel=On Completeness and Soundness in Interactive Proof Systems |werk=Advances in Computing Research |datum=1989 |format=PDF; 155 kB |sprache=en |archiv-url=https://web.archive.org/web/20151127155929/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.9412&rep=rep1&type=pdf |archiv-datum=2015-11-27 |abruf=2008-08-27}}</ref>

Sie wurden 1985 von [[Shafi Goldwasser]], [[Charles Rackoff]] und [[Silvio Micali]] eingeführt (wobei Preprints bis auf 1982 zurückgingen) und unabhängig von [[László Babai]] 1985, der darüber später ausführlich mit [[Shlomo Moran]] veröffentlichte.<ref>{{Internetquelle |autor=László Babai, Shlomo Moran |url=https://dl.acm.org/doi/abs/10.1016/0022-0000%2888%2990028-1 |titel=Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes |werk=Journal of Computer and System Sciences, Band 36, Nr. 2 |datum=1988 |seiten=254–276 |sprache=en |abruf=2010-08-24}}</ref> Die Autoren erhielten dafür den ersten [[Gödel-Preis]] 1993.

== Formal ==
Ein '''interaktives Beweissystem''' (IBS) ist ein Protokoll <math>(P, V)</math> zwischen einem Beweisführer (Prover) und einem Prüfer (Verifier). Dabei ist <math>P</math> eine [[PSPACE]]-Maschine und <math>V</math> eine [[probabilistische Turingmaschine]] mit [[Polynomialzeit|polynomieller Zeitschranke]]. Beweisführer und Prüfer erhalten die gleiche Eingabe <math>x, |x| = n,</math> auf einem read-only Band. Das Protokoll umfasst polynomiell viele <math>p(n)</math> Runden, in denen nur polynomiell viele Nachrichten ausgetauscht werden dürfen.<ref>{{Internetquelle |autor=Shafi Goldwasser, Silvio Micali, Charles Rackoff |url=https://dl.acm.org/doi/10.1145/22145.22178 |titel=The knowledge complexity of interactive proof systems |werk=SIAM Journal on Computing |datum=1989 |seiten=291–304 |sprache=en |abruf=2008-08-27}}</ref> <math>(P, V) = (p_1, v_1, p_2, v_2, ..., p_{p(n)}, v_{p(n)})</math>
in der letzten Runde akzeptiert oder verwirft dann der Prüfer (ja/nein bzw. 1/0).

Ein <math>\mathrm{IBS}(P, V)</math> entscheidet eine [[Formale Sprache|Sprache]] <math>L \subseteq \Sigma^*</math>, falls für alle Eingaben <math>x \in \Sigma^*</math> gilt:
# Ist <math>x \in L</math> so akzeptiert der Prüfer mit [[Wahrscheinlichkeitstheorie|Wahrscheinlichkeit]] <math>P(x \in L) \leq (1 - 2^{-n})</math>
# Ist <math>x \notin L</math> so gibt es kein <math>\mathrm{IBS}(P, V)</math>, das den Prüfer mit Wahrscheinlichkeit <math>P(x \in L) > 2^{-n}</math> akzeptieren lässt.<ref name="Fourer" />

== Beispiel ==
'''Eingabe:''' Zwei Graphen <math>G_1, G_2</math>
# Arthur beginnt: Er wählt per Zufall einen der beiden Graphen (<math>G_1</math> oder <math>G_2</math>) aus und permutiert die Benennung der Knoten zu einem neuen, isomorphen Graph <math>H</math>. Diesen Graphen übermittelt er Merlin.
# Merlin rechnet die Permutationen von <math>H</math> zurück und kann somit entscheiden, ob Arthur ursprünglich Graph <math>G_1</math> oder <math>G_2</math> 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 <math>G_1</math> und <math>G_2</math> isomorph sind,
so kann Merlin nicht entscheiden, welchen Ursprung <math>H</math> 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 [[Polynomialzeit|P]]-beschränkt. Das Beispiel wurde von [[László Babai]] zuerst beschrieben.<ref>{{Internetquelle |autor=László Babai |url=https://dl.acm.org/doi/10.1145/22145.22192 |titel=Trading group theory for randomness |werk=Proceedings of the Seventeenth Annual Symposium on the Theory of Computing |hrsg=ACM |datum=1985 |seiten=421–429 |sprache=en |abruf=2008-08-27}}</ref>

== Komplexitätsklasse ==
Für die Komplexitätsklasse '''IP''', die alle Entscheidungsprobleme enthält, die ein interaktives Beweissystem besitzen, gilt: '''IP''' = '''[[PSPACE]]'''
==Verallgemeinerung==
Eine Verallgemeinerung ist MIP, Multiprover Interactive Proof System, mit mehr als einem Beweiser.

== Einzelnachweise ==
<references />

[[Kategorie:Komplexitätstheorie]]

Interaktives Beweissystem - Versionsgeschichte

imported>Siegbert v2: QS: tote Links repariert / ref-Tag nach Satzzeichen