Schränkt das Erfordernis der Eindeutigkeit gültiger Antworten für Merlin die Leistungsfähigkeit der Arthur-Merlin-Protokolle ein?

15

Präambel.

Die Komplexitätsklasse AM sind die Probleme, die durch ein interaktives Zwei-Runden-Beweissystem zwischen einem Prüfer "Merlin" und einem Prüfer "Arthur" gelöst werden können. Ein Problem - das eine Eigenschaft eines Objekts X testet - liegt in AM vor, wenn:

  • In JA- Fällen kann Arthur für eine zufällige "Challenge" -Nachricht (mit polynomischer Länge) mit hoher Wahrscheinlichkeit eine Antwort (mit polynomischer Länge) formulieren, anhand derer Arthur nachweisen kann, dass X die Eigenschaft besitzt.

  • Für NO Fälle für eine zufällige Herausforderungsnachricht Arthur, mit hohen Wahrscheinlichkeit Merlin erzeugt , kann keine Antwort formulieren , die als Beweis für die Eigenschaft verwendet werden , können auf getesteten X .

- Die beschriebene Klasse ändert sich nicht, wenn wir von Merlin verlangen, dass sie nicht nur mit hoher Wahrscheinlichkeit eine nützliche Antwort gibt, sondern auch für jede Herausforderung, die Arthur möglicherweise stellt. In diesem Fall könnten wir sagen, dass Merlins Antwort immer für JA- Instanzen gültig sein muss , und was Arthur testet, ist die Gültigkeit der Antwort. Wenn Merlin also jemals eine ungültige Antwort ausgibt, weiß Arthur, dass es sich bei der Probleminstanz um eine NO- Instanz handelt. Dies ist die Einstellung, die ich am liebsten in Betracht ziehen würde.

Ein Beispiel ist "Graph Non-Isomorphism": Wenn die Graphen G und H denselben Satz von Scheitelpunktbezeichnungen haben, kann Arthur zufällig einen der Graphen auswählen und eine "verschlüsselte" Version F erzeugen, indem seine Scheitelpunktbezeichnungen permutiert werden und eine Präsentation an Merlin gesendet wird . Wenn die beiden nicht-isomorphen Graphen sind, können Merlin , welche identifizieren , G oder H Arthur entschieden durch Bestimmen , ob F  ≅  G oder F  ≅  H , und durch die Identifizierung , welche der beiden reagieren kann F isomorph ist. Wenn die beiden Graphen G und H jedoch isomorph sind, kann Merlin nicht unterscheiden, welcher Graph vorliegtF kam von, und jede Antwort, die er gibt, kann nur zufällig richtig sein. Somit kann Merlin für JA- Instanzen immer eine gültige Antwort auf jede Herausforderung senden. für NO Instanzen jeder Antwort , die Merlin vielleicht wird mit hohen Wahrscheinlichkeit ungültig senden.

In dem obigen Problem gibt es nicht nur eine gültige Antwort, die Merlin für jede Herausforderung an Arthur ausgeben kann, sondern es gibt auch eine eindeutige gültige Antwort: Geben Sie  an, welche von G oder H Arthur gewählt hat, vorausgesetzt, dies kann bestimmt werden durch Identifizieren, welches zu F isomorph ist .

Frage.

Ergibt das Auferlegen einer Einschränkung in dieser Richtung - dass es für JA- Instanzen, für jede von Arthur gesendete Herausforderung, genau eine gültige Antwort für Merlin gibt - eine restriktivere Klasse im Sinne einer Klasse, von der nicht bekannt ist, dass sie AM entspricht ?

Niel de Beaudrap
quelle
Bevor ich darüber nachdenke, ob es gleich AM ist oder nicht, kann ich nicht einmal nachweisen, dass NP in Ihrer Klasse enthalten ist.
Tsuyoshi Ito
1
Wenn Merlin nur mit hoher Wahrscheinlichkeit eine gültige Antwort erhalten soll, enthält die Klasse NP (und vermutlich auch AM): Wir können Arthur veranlassen, die Valiant-Vazirani-Reduktion zu Unique-SAT durchzuführen.
Emil Jeřábek unterstützt Monica am
@Emil: Ich verstehe, dass, wenn "hohe Wahrscheinlichkeit" 1 / poly ist, es möglich ist, diese Wahrscheinlichkeit beispielsweise auf eine Konstante zu erhöhen?
Tsuyoshi Ito
Fair genug, das ist eigentlich eine eher geringe Wahrscheinlichkeit. Ich weiß nicht, wie ich es zu einer Konstante machen soll.
Emil Jeřábek unterstützt Monica am
1
Ziehen Sie Protokolle für öffentliche Münzen oder für private Münzen in Betracht? Aus der Definition geht hervor, dass Sie an Protokolle für öffentliche Münzen denken, aber das von Ihnen beschriebene Protokoll für den Nicht-Isomorphismus von Graphen ist kein Protokoll für öffentliche Münzen.
Tsuyoshi Ito

Antworten:

1

mnCnpH(p)=0H(a0,a1,,an)mmodp

modppmodppp

pCnpa11/e

In dem obigen Problem gibt es also nicht nur eine gültige Antwort, die Merlin für jede Herausforderung an Arthur senden kann, sondern es kann auch eine große Anzahl gültiger Antworten geben.

pp

Mark S
quelle