In der rechenbetonten Kompliziertheitstheorie ist ein interaktives Probesystem eine abstrakte Maschine dass Musterberechnung als der Austausch von Nachrichten zwischen zwei Parteien. Die Parteien, der verifier und der prover, wirken aufeinander, indem sie Nachrichten austauschen, um festzustellen, ob eine gegebene Schnur einer Sprache gehört oder nicht. Der prover ist allmächtig und besitzt unbegrenzte rechenbetonte Mittel, aber kann nicht vertraut werden, während der verifier Berechnungsmacht begrenzt hat. Nachrichten werden zwischen dem verifier und prover gesandt, bis der verifier eine Antwort auf das Problem hat und sich "überzeugt" hat, dass es richtig ist.

Alle interaktiven Probesysteme haben zwei Voraussetzungen:

• Vollständigkeit: Wenn die Behauptung wahr ist, wird der ehrliche verifier (d. h. ein im Anschluss an das Protokoll richtig) von dieser Tatsache durch einen ehrlichen prover überzeugt sein.
• Stichhaltigkeit: Wenn die Behauptung falsch ist, kann kein prover, selbst wenn sie dem Protokoll nicht folgt, den ehrlichen verifier überzeugen, dass es wahr ist, außer mit etwas kleiner Wahrscheinlichkeit.

Bemerken Sie, dass wir uns nicht sorgen, was geschieht, wenn der verifier unehrlich ist; wir vertrauen dem verifier.

Die spezifische Natur des Systems, und so die Kompliziertheitsklasse von Sprachen kann es anerkennen, hängt ab, welche Grenzen auf den verifier gestellt werden, sowie welche geistige Anlagen es - zum Beispiel gegeben wird, hängen die meisten interaktiven Probesysteme kritisch von der Fähigkeit des verifier ab, zufällige Wahlen zu machen. Es hängt auch von der Natur der Nachrichten ausgetauscht ab - wie viel und was sie enthalten können. Wie man gefunden hat, haben interaktive Probesysteme einige überraschend tiefe Implikationen für traditionelle definierte Kompliziertheitsklassen mit nur einer Maschine gehabt. Die Hauptkompliziertheitsklassen, die interaktive Probesysteme beschreiben, sind AM und IP.

NP

Die Kompliziertheitsklasse NP kann als ein sehr einfaches Probesystem angesehen werden. In diesem System ist der verifier eine deterministische, polynomisch-malige Maschine (eine P Maschine). Das Protokoll ist:

• Der prover schaut auf den Eingang und schätzt die Lösung mit seiner unbegrenzten Macht und gibt ein Probezertifikat der polynomischen Größe zurück.
• Der verifier prüft nach, dass das Zertifikat in der deterministischen polynomischen Zeit gültig ist. Wenn es gültig ist, akzeptiert es; sonst weist es zurück.

Im Fall, wo ein gültiges Probezertifikat besteht, ist der prover immer im Stande, den verifier durch das Geben ihm dieses Zertifikats akzeptieren zu lassen. Im Fall, wo es kein gültiges Probezertifikat jedoch gibt, ist der Eingang nicht auf der Sprache und keinem prover, jedoch böswillig es ist, kann den verifier sonst überzeugen, weil jedes Probezertifikat zurückgewiesen wird.

Arthur-Merlin und Protokolle von Merlin-Arthur

Obwohl NP als das Verwenden der Wechselwirkung erst als 1985 angesehen werden kann, dass das Konzept der Berechnung durch die Wechselwirkung von zwei unabhängigen Gruppen von Forschern konzipiert wurde. Eine Annäherung, durch László Babai, der "Handelsgruppentheorie für die Zufälligkeit veröffentlicht hat", hat die Klassenhierarchie von Arthur Merlin (AM) definiert. In dieser Präsentation ist Arthur (der verifier) ein probabilistic, polynomisch-malige Maschine, während Merlin (der prover) unbegrenzte Mittel hat.

Der Klassenmagister artium ist insbesondere eine einfache Generalisation der NP Wechselwirkung oben, in der der verifier probabilistic statt des deterministischen ist. Außerdem anstatt zu verlangen, dass die verifier immer gültige Zertifikate akzeptieren und ungültige Zertifikate zurückweisen, ist es nachsichtiger:

• Vollständigkeit: Wenn die Schnur auf der Sprache ist, muss der prover im Stande sein, ein solches Zertifikat zu geben, dass der verifier mit der Wahrscheinlichkeit mindestens 2/3 (abhängig von zufälligen Wahlen des verifier) akzeptieren wird.
• Stichhaltigkeit: Wenn die Schnur nicht auf der Sprache ist, wird kein prover, jedoch böswillig, im Stande sein, den verifier zu überzeugen, die Schnur mit der Wahrscheinlichkeit zu akzeptieren, die 1/3 zu weit geht.

Diese Maschine ist potenziell stärker als ein gewöhnliches NP Wechselwirkungsprotokoll, und die Zertifikate sind nicht weniger praktisch, um nachzuprüfen, da BPP Algorithmen als das Entziehen praktischer Berechnung betrachtet werden (sieh BPP).

Öffentliche Münzen gegen private Münzen

In derselben Konferenz, wo Babai sein Probesystem für den Magister artium definiert hat, haben Shafi Goldwasser, Silvio Micali und Charles Rackoff eine Zeitung veröffentlicht, die das interaktive Probesystem IP [f (n)] definiert. Das hat dieselben Maschinen wie das Protokoll des Magisters artium, außer dass f (n) Runden für einen Eingang der Größe n erlaubt wird. In jeder Runde führt der verifier Berechnung durch und passiert eine Nachricht an den prover, und der prover führt Berechnung durch und passiert Information zurück zum verifier. Am Ende muss der verifier seine Entscheidung treffen. Zum Beispiel, in einem IP [3] Protokoll, würde die Folge VPVPVPV sein, wo V eine Verifier-Umdrehung ist und P eine Prover-Umdrehung ist.

In Protokollen von Arthur-Merlin hat Babai eine ähnliche Klasse AM [f (n)] definiert, der f (n) Runden erlaubt hat, aber er hat eine Extrabedingung auf die Maschine gestellt: Der verifier muss dem prover alle zufälligen Bit zeigen, die es in seiner Berechnung verwendet. Das Ergebnis besteht darin, dass der verifier nichts vor dem prover "verbergen" kann, weil der prover stark genug ist, um alles vorzutäuschen, was der verifier tut, wenn es das weiß, welche zufällige Bit es verwendet hat. Wir nennen das ein öffentliches Münzprotokoll, weil die zufälligen Bit ("Münzflips") zu beiden Maschinen sichtbar sind. Die IP-Annäherung wird ein privates Münzprotokoll im Vergleich genannt.

Das wesentliche Problem mit öffentlichen Münzen besteht darin, dass, wenn der prover den verifier böswillig überzeugen möchte, eine Schnur zu akzeptieren, die nicht auf der Sprache ist, es scheint, dass der verifier im Stande sein könnte, seine Pläne durchzukreuzen, wenn es seinen inneren Staat davor verbergen kann. Das war eine primäre Motivation im Definieren der IP Probesysteme.

1986 haben Goldwasser und Sipser vielleicht überraschend gezeigt, dass die Fähigkeit des verifier, Münzflips vor dem prover zu verbergen, es wenig Nutzen schließlich, darin tut, kann ein Publikum-Münzprotokoll von Arthur-Merlin mit noch nur zwei Runden alle gleich Sprachen anerkennen. Das Ergebnis besteht darin, dass öffentliche Münze und Protokolle der privaten Münze grob gleichwertig sind. Tatsächlich, weil sich Babai 1988, AM [k] =AM für den ganzen unveränderlichen k zeigt, so der IP sind [k] im Vorteil gegenüber AM.

Um die Macht dieser Klassen zu demonstrieren, denken Sie das Graph-Isomorphismus-Problem, das Problem der Bestimmung, ob es möglich ist, die Scheitelpunkte eines Graphen zu permutieren, so dass es zu einem anderen Graphen identisch ist. Dieses Problem ist in NP, da das Probezertifikat die Versetzung ist, die die Graphen gleich macht. Es stellt sich dass der heraus

die Ergänzung des Graph-Isomorphismus-Problems, ein co-NP Problem, das nicht bekannt ist, in NP zu sein, hat einen Algorithmus von AM und die beste Weise zu sehen, dass es über einen privaten Münzalgorithmus ist.

IP

Private Münzen können nicht nützlich sein, aber mehr Runden der Wechselwirkung sind nützlich. Wenn wir dem probabilistic verifier Maschine und der allmächtige prover erlauben, für eine polynomische Zahl von Runden aufeinander zu wirken, bekommen wir die Klasse von Problemen genannt IP.

1992 hat Adi Shamir in einem der Hauptergebnisse der Kompliziertheitstheorie offenbart, dass IP PSPACE, der Klasse von Problemen gleichkommt, die durch eine gewöhnliche deterministische Maschine von Turing im polynomischen Raum lösbar sind.

QIP

Wenn wir den Elementen des Systems erlauben, Quant-Berechnung zu verwenden, wird das System ein Quant interaktives Probesystem genannt, und die entsprechende Kompliziertheitsklasse wird QIP genannt. Wie man glaubt, hat eine Reihe von neuen Ergebnissen, die in einer 2010 veröffentlichten Zeitung kulminieren, das QIP = PSPACE demonstriert.

Nullkenntnisse

Nicht nur können interaktive Probesysteme Probleme beheben, die nicht geglaubt sind, in NP, aber unter Annahmen über die Existenz von Einwegfunktionen zu sein, ein prover kann den verifier der Lösung überzeugen, ohne jemals die verifier Information über die Lösung zu geben. Das ist wichtig, wenn dem verifier die volle Lösung nicht anvertraut werden kann. Zuerst scheint es unmöglich, dass der verifier überzeugt sein konnte, dass es eine Lösung gibt, als der verifier kein Zertifikat, aber solche Beweise, bekannt gesehen hat, weil, wie man tatsächlich glaubt, Nullkenntnisse-Beweise für alle Probleme in NP bestehen und in der Geheimschrift wertvoll sind. Nullkenntnisse-Beweise wurden zuerst in der ursprünglichen 1985-Zeitung auf IP von Goldwasser, Micali und Rackoff erwähnt, aber das Ausmaß ihrer Macht wurde von Oded Goldreich, Silvio Micali und Avi Wigderson gezeigt.

MIP

Eine Absicht der Entwerfer von IP war, das stärkstmögliche interaktive Probesystem zu schaffen, und zuerst scheint es, dass es stärker nicht gemacht werden kann, ohne das verifier stärkere und so unpraktisch zu machen. Goldwasser. hat das in ihren 1988 "Interaktiven prover Vielbeweisen überwunden: Wie man Hartnäckigkeitsannahmen entfernt", der eine Variante von IP genannt MIP definiert, in dem es zwei unabhängige provers gibt. Die zwei provers können nicht kommunizieren, sobald der verifier begonnen hat, Nachrichten ihnen zu senden. Da es leichter ist zu erzählen, ob ein Verbrecher lügt, wenn er und sein Partner in getrennten Zimmern befragt werden, ist es beträchtlich leichter, einen böswilligen prover zu entdecken, der versucht, den verifier ins Annehmen einer Schnur nicht auf der Sprache zu beschwindeln, wenn es einen anderen prover gibt, mit dem es zweimal kontrollieren kann.

Tatsächlich ist das so nützlich, dass Babai, Fortnow und Lund im Stande gewesen sind, dass MIP = NEXPTIME, die Klasse aller Probleme zu zeigen, die durch eine nichtdeterministische Maschine in der Exponentialzeit, einer sehr großen Klasse lösbar sind. NEXPTIME enthält PSPACE und wird geglaubt, PSPACE ausschließlich zu enthalten. Das Hinzufügen einer unveränderlichen Zahl von zusätzlichem provers darüber hinaus zwei ermöglicht Anerkennung von nicht mehr Sprachen. Dieses Ergebnis hat für den berühmten PCP Lehrsatz den Weg geebnet, der, wie man betrachten kann, eine "schuppige unten" Version dieses Lehrsatzes ist.

MIP hat auch das nützliche Eigentum, dass Nullkenntnisse-Beweise für jede Sprache in NP ohne die Annahme von Einwegfunktionen beschrieben werden können, dass IP machen muss. Das hat das Beziehen auf das Design nachweisbar unzerbrechlicher kryptografischer Algorithmen. Außerdem kann ein MIP Protokoll alle Sprachen in IP in nur einer unveränderlichen Zahl von Runden anerkennen, und wenn ein Drittel prover hinzugefügt wird, kann es alle Sprachen in NEXPTIME in einer unveränderlichen Zahl von Runden anerkennen, wieder seine Macht über IP zeigend.

PCP

Während die Entwerfer von IP Generalisationen der interaktiven Probesysteme von Babai gedacht haben, haben andere Beschränkungen gedacht. Ein sehr nützliches interaktives Probesystem ist PCP (f (n), g (n)), der eine Beschränkung des Magisters artium ist, wo Arthur nur f (n) zufällige Bit verwenden kann und nur g (n) Bit des Probezertifikats untersuchen kann, das von Merlin gesandt ist (im Wesentlichen zufälligen Zugang verwendend).

Es gibt mehrere Easy-Prove-Ergebnisse über verschiedene PCP Klassen. PCP (0, poly), die Klasse von polynomisch-maligen Maschinen ohne Zufälligkeit, aber Zugang zu einem Zertifikat, ist gerade NP. PCP (poly, 0), ist die Klasse von polynomisch-maligen Maschinen mit dem Zugang zu polynomisch vielen zufälligen Bit Handelsgesellschaft. Aroras erstes Hauptergebnis und Safras bestand dass PCP (Klotz, Klotz) = NP darin; stellen Sie einen anderen Weg, wenn der verifier im NP Protokoll beschränkt wird, nur O zu wählen (loggen Sie n) Bit des Probezertifikats, um auf zu schauen, wird das keinen Unterschied machen, so lange es O hat (loggen Sie n) zufällige Bit, um zu verwenden.

Außerdem behauptet der PCP Lehrsatz, dass die Zahl von Probezugängen den ganzen Weg unten zu einer Konstante gebracht werden kann. D. h. NP = PCP (Klotz, O (1)). Sie haben diese wertvolle Charakterisierung von NP verwendet, um zu beweisen, dass Annäherungsalgorithmen für die Optimierungsversionen von bestimmten NP-complete Problemen wenn P = NP nicht bestehen. Solche Probleme werden jetzt im als Härte der Annäherung bekannten Feld studiert.

Lehrbücher

• Arora, Sanjeev; Barak, Boaz, "Kompliziertheitstheorie: Eine Moderne Annäherung", Universität von Cambridge Presse, März 2009.

• Abschnitt 10.4: Interaktive Probesysteme, Seiten 354-366.

• Abschnitt 19.2: Spiele gegen die Natur und interaktiven Protokolle, Seiten 469-480.

Siehe auch

• Orakel (Informatik)

Außenverbindungen

• Dexter Kozen. Interaktive Beweise. CS682 Frühling 2004 hält Zeichen Vorlesungen. Abteilung der Informatik, Universität von Cornell.
• Kompliziertheitszoo:
• MAGISTER ARTIUM, MAGISTER ARTIUM', MAEXP, MAE
• AM, AMEXP, schneidet AM co-AM, AM, coAM, BP durch · NP
• QMA, QMA +, QMA (2), QMA, QMAM
• IP, MIP, IPP, QIP, QIP (2), compIP, frIP
• PCP (r (n), q (n))
• Larry Gonick. "Positiver Beweis?". Ein Cartoon über interaktive Probesysteme.