Arthur -Merlin -Protokoll

Im Computerkomplexitätstheorie, ein Arthur -Merlin -Protokoll, Vorgestellt von Babai (1985), ist ein Interaktives Proof -System in dem die Münzen des Verifizierers als öffentlich gezwungen werden (d. H. Auch dem Prover bekannt). Goldwasser & Sipser (1986) bewiesen, dass alle (formell) Sprachen Mit interaktiven Beweisen der willkürlichen Länge mit privaten Münzen haben auch interaktive Beweise mit öffentlichen Münzen.

Angesichts von zwei Teilnehmern des Protokolls namens Arthur bzw. Merlin ist die grundlegende Annahme, dass Arthur ein Standardcomputer (oder ein Verifizierer) ist, das mit einem ausgestattet ist Geräte für zufällige Nummer generieren, während Merlin effektiv ein ist Orakel mit unendlicher Rechenleistung (auch als Prover bekannt). Merlin ist jedoch nicht unbedingt ehrlich, daher muss Arthur die von Merlin bereitgestellten Informationen als Reaktion auf die Fragen von Arthur analysieren und das Problem selbst entscheiden. Ein Problem wird von diesem Protokoll als lösbar angesehen, wenn Merlin immer dann einige Antworten hat, die dazu führen, dass Arthur zumindest akzeptiert wird 2⁄3 der Zeit und wenn die Antwort "Nein" ist, wird Arthur niemals mehr akzeptieren als 1⁄3 der ganzen Zeit. Somit wirkt Arthur als probabilistische Polynom-Zeit-Überprüfung, vorausgesetzt, es wird Polynomzeit zugeteilt, um seine Entscheidungen und Abfragen zu treffen.

Ma

Das einfachste Protokoll ist das 1-Message-Protokoll, in dem Merlin Arthur eine Nachricht sendet, und dann entscheidet Arthur, ob eine probabilistische Polynomzeitberechnung angenommen wird oder nicht. (Dies ähnelt der auf nach auf Verifikern basierenden Definition von NP. Der einzige Unterschied besteht darin Wirft seine Münzen erst nach Erhalt von Merlins Nachricht. Dieses Protokoll heißt Ma. Informell a Sprache L ist in Ma Wenn für alle Saiten in der Sprache ein polynomischer Beweis dafür vorliegt, dass Merlin Arthur mit hoher Wahrscheinlichkeit von dieser Tatsache überzeugen kann, und für alle Strings, die nicht in der Sprache nicht in der Sprache sind, gibt es keinen Beweis, der Arthur mit hoher Wahrscheinlichkeit überzeugt.

Formal die Komplexitätsklasse Ma ist die Reihe von Entscheidungsproblemen, die in der Polynomzeit von einem Arthur -Merlin -Protokoll entschieden werden können, in dem Merlins einzige Bewegung jeder Berechnung von Arthur vorausgeht. Mit anderen Worten, eine Sprache L ist in Ma Wenn es eine polynomiale probabilistische Turing-Maschine gibt M und Polynome p, q so dass für jede Eingangszeichenfolge x von Länge n = |x|,

• wenn x ist in L, dann $oder (x, y, z) = 1) \ Geq 2/3,}$
• wenn x ist nicht in L, dann $oder (x, y, z) = 0) \ Geq 2/3.}$

Die zweite Bedingung kann alternativ als geschrieben werden

• wenn x ist nicht in L, dann $oder (x, y, z) = 1) \ Leq 1/3.}$

Um dies mit der obigen informellen Definition zu vergleichen, z ist der angebliche Beweis von Merlin (dessen Größe durch ein Polynom begrenzt ist) und y ist die zufällige Zeichenfolge, die Arthur verwendet, der ebenfalls polynomisch begrenzt ist.

BIN

Das Komplexitätsklasse BIN (oder AM [2]) ist der Satz von Entscheidungsprobleme Dies kann in der Polynomzeit durch ein Arthur -Merlin -Protokoll mit zwei Nachrichten entschieden werden. Es gibt nur ein Abfrage-/Antwortpaar: Arthur wirft einige zufällige Münzen und sendet das Ergebnis von alle Seine Münze wirft Merlin auf, Merlin antwortet mit einem angeblichen Beweis, und Arthur überprüft den Beweis deterministisch. In diesem Protokoll darf Arthur nur die Ergebnisse von Münzwerfen an Merlin senden, und im letzten Stadium muss Arthur entscheiden, ob er nur seine zuvor erzeugten zufälligen Münzflips und Merlins Nachricht akzeptieren oder ablehnen soll.

Mit anderen Worten, eine Sprache L ist in BIN Wenn es eine polynomiale deterministische Turing-Maschine gibt M und Polynome p, q so dass für jede Eingangszeichenfolge x von Länge n = |x|,

• wenn x ist in L, dann $oder (x, y, z) = 1) \ Geq 2/3,}$
• wenn x ist nicht in L, dann $oder (x, y, z) = 0) \ Geq 2/3.}$

Die zweite Bedingung hier kann als umgeschrieben werden als

• wenn x ist nicht in L, dann $oder (x, y, z) = 1) \ Leq 1/3.}$

Wie oben, z ist der angebliche Beweis von Merlin (dessen Größe durch ein Polynom begrenzt ist) und y ist die zufällige Zeichenfolge, die Arthur verwendet, der ebenfalls polynomisch begrenzt ist.

Die Komplexitätsklasse BIN[k] ist die Reihe von Problemen, die in der Polynomzeit entschieden werden können, mit k Abfragen und Antworten. BIN wie oben definiert ist AM [2]. AM [3] Würde mit einer Nachricht von Merlin an Arthur beginnen, dann eine Nachricht von Arthur an Merlin und schließlich eine Nachricht von Merlin an Arthur. Die letzte Nachricht sollte immer von Merlin nach Arthur sein, da sie Arthur nie hilft, eine Nachricht an Merlin zu senden, nachdem sie seine Antwort entschieden hat.

Eigenschaften

Bekannte Beziehungen von Ma und BIN mit anderen Komplexitätsklassen. Ein Pfeil aus der Klasse A zur Klasse B meint A ist eine Teilmenge von B.

• Beide Ma und BIN bleiben unverändert, wenn ihre Definitionen geändert werden, um eine perfekte Vollständigkeit zu erfordern, was bedeutet, dass Arthur mit Wahrscheinlichkeit 1 (anstelle von 2/3) annimmt, wenn x ist in der Sprache.^[1]
• Für jede Konstante k ≥ 2, die Klasse BIN[k] ist gleich AM [2]. Wenn k kann polynomial mit der Eingangsgröße, der Klasse, zusammenhängen BIN[Poly (Poly (n)] ist gleich der Klasse, IP, von dem bekannt ist, dass er gleich ist PSPACE und es wird allgemein angenommen, dass sie stärker ist als die Klasse AM [2].
• Ma ist in BIN, seit BIN[3] enthält Ma: Arthur kann nach Erhalt von Merlins Zertifikat die erforderliche Anzahl von Münzen umdrehen, sie an Merlin senden und die Antwort ignorieren.
• Es ist offen, ob BIN und Ma sind anders. Unter plausiblen Schaltkreis unteren Grenzen (ähnlich denen, die implizieren P=BPP), sie sind beide gleich zu Np.^[2]
• BIN ist dasselbe wie die Klasse Bpúnp wo Bp bezeichnet den probabilistischen Operator mit begrenztem Erreger. Ebenfalls, ${\ displayStyle \ existiert \ cdot {\ mathsf {bpp}}}$ (auch geschrieben als Existiertbpp) ist eine Teilmenge von Ma. Ob Ma ist gleich ${\ displayStyle \ existiert \ cdot {\ mathsf {bpp}}}$ ist eine offene Frage.
• Die Konvertierung in ein privates Münzprotokoll, in dem Merlin das Ergebnis von Arthurs zufälligen Entscheidungen vorhersagen kann, wird die Anzahl der Wechselwirkungsrunden im allgemeinen Fall höchstens 2 erhöhen. Also die private Coin-Version von BIN ist gleich der öffentlichen Version.
• Ma enthält beides Np und BPP. Für BPP ist dies unmittelbar, da Arthur Merlin einfach ignorieren und das Problem direkt lösen kann. Für NP muss Merlin nur Arthur ein Zertifikat senden, das Arthur in der Polynomzeit deterministisch validieren kann.
• Beide Ma und BIN sind in der enthalten Polynomhierarchie. Im Speziellen, Ma ist im Schnittpunkt von σ enthalten₂^P und π₂^P und BIN ist in π enthalten₂^P. Sogar mehr, Ma ist in Unterklasse enthalten S^P
  ₂,^[3] Eine Komplexitätsklasse, die "symmetrische Wechsel" ausdrückt. Dies ist eine Verallgemeinerung von SIPser -Lautemann -Theorem.
• BIN ist in NP/Poly, die Klasse der Entscheidungsprobleme, die in nicht deterministischer Polynomzeit mit einer Polynomgröße berechnet werden können Rat. Der Beweis ist eine Variation von Adleman's Theorem.
• Ma ist in Pp; Dieses Ergebnis ist auf Vereshchagin zurückzuführen.^[4]
• Ma ist in seiner Quantenversion enthalten, QMA.^[5]
• BIN enthält die Problem zu entscheiden, ob zwei Grafiken sind nicht isomorph. Das Protokoll mit privaten Münzen ist Folgendes und kann in ein öffentliches Münzprotokoll umgewandelt werden. Zwei Grafiken G und H, Arthur wählt zufällig einen von ihnen und wählt eine zufällige Permutation seiner Eckpunkte, wobei die permutierte Grafik dargestellt wird I nach Merlin. Merlin muss antworten, wenn I wurde von G oder H. Wenn die Diagramme nicht isomorph sind, kann Merlin mit voller Gewissheit antworten (indem man überprüft, ob I ist isomorph zu G). Wenn die Grafiken jedoch isomorph sind, ist es beides möglich, dass dies möglich ist G oder H wurde verwendet, um zu erstellen Iund ebenso wahrscheinlich. In diesem Fall hat Merlin keine Möglichkeit, sie zu unterscheiden, und kann Arthur höchst 1/2 überzeugen, und dies kann durch Wiederholung auf 1/4 verstärkt werden. Dies ist in der Tat a null Wissensbeweis.
• Wenn BIN enthält Conp dann PH = BIN. Dies ist ein Beweis dafür, dass das Graph-Isomorphismus wahrscheinlich nicht np-komplett ist, da es einen Zusammenbruch der Polynomhierarchie impliziert.
• Es ist bekannt, vorausgesetzt Erhdas für jeden d Das Problem "bei einer Sammlung von multivarariaten Polynomen ${\ displayStyle f_ {i}}$ jeweils mit ganzzahligen Koeffizienten und höchstens Grad d, haben sie eine gemeinsame Komplex Null? "ist in BIN.^[6]

Verweise

Literaturverzeichnis

• Babai, László (1985), "Handelsgruppentheorie für Zufälligkeit", STOC '85: Verfahren des siebzehnten jährlichen ACM -Symposiums über die Theorie des Computers, ACM, S. 421–429, ISBN 978-0-89791-151-1.
• Goldwasser, Shafi; Sipser, Michael (1986), "Private Münzen gegen öffentliche Münzen in interaktiven Proof -Systemen", STOC '86: Verfahren des achtzehnten jährlichen ACM -Symposiums über die Theorie des Computers, ACM, S. 59–68, ISBN 978-0-89791-193-1.
• Arora, Sanjeev; Barak, Boaz (2009), Rechenkomplexität: ein moderner Ansatz, Cambridge, ISBN 978-0-521-42426-4.
• Madhu Sudans MIT -Kurs über fortgeschrittene Komplexität

Externe Links

• Komplexitätszoo: Ma
• Komplexitätszoo: BIN