Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
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 László 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.
Ein interaktives Beweissystem (IBS) ist ein Protokoll zwischen einem Beweisführer (Prover) und einem Prüfer (Verifier). Dabei ist eine PSPACE-Maschine und eine probabilistische Turingmaschine mit polynomieller Zeitschranke. Beweisführer und Prüfer erhalten die gleiche Eingabe auf einem read-only Band. Das Protokoll umfasst polynomiell viele Runden, in denen nur polynomiell viele Nachrichten ausgetauscht werden dürfen.[3] in der letzten Runde akzeptiert oder verwirft dann der Prüfer (ja/nein bzw. 1/0).
Ein entscheidet eine Sprache , falls für alle Eingaben gilt:
Eingabe: Zwei Graphen
Es ist bekanntermaßen schwierig herauszufinden, ob zwei Graphen isomorph sind (siehe Isomorphie von Graphen). Wenn und isomorph sind, so kann Merlin nicht entscheiden, welchen Ursprung hat.
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[4].
Für die Komplexitätsklasse IP, die alle Entscheidungsprobleme enthält, die ein interaktives Beweissystem besitzen, gilt: IP = PSPACE
Eine Verallgemeinerung ist MIP, Multiprover Interactive Proof System, mit mehr als einem Beweiser.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.