Die Gleichwertigkeit zweier Definitionen von Vollständigkeit und Solidität in interaktiven Beweissystemen

11

Die Vollständigkeit und Solidität in interaktiven Proofsystemen wird informell definiert als:

  • Vollständigkeit: Wenn eine Aussage wahr ist, die ehrlich Prover die überzeugen kann ehrlich Verifizierer dieser Tatsache whp .

  • Solidität: Wenn eine Aussage falsch ist, kann der Betrüger den ehrlichen Prüfer (von der Gültigkeit der falschen Aussage) nicht überzeugen

Der Begriff "whp" wird entweder als "mit einer Wahrscheinlichkeit größer als (sagen wir) 2/3" oder "mit einer Wahrscheinlichkeit größer als der Kehrwert eines Polynoms" interpretiert. Es scheint für die folgende Diskussion unerheblich, welche Interpretation von "whp" zu wählen ist.

Der schwierige Teil ist, wie die Wahrscheinlichkeit berechnet wird: In einigen Quellen wird die Wahrscheinlichkeit über die zufälligen Münzen sowohl des Prüfers als auch des Verifizierers übernommen. In anderen Quellen wird die Wahrscheinlichkeit nur über die zufälligen Münzen des Verifizierers berechnet. Letzteres ist normalerweise gerechtfertigt als: "Was auch immer die zufälligen Münzen des Prüfers sind, der Prüfer trifft die richtige Entscheidung."

Beide Definitionen der Wahrscheinlichkeit erscheinen mir gleichwertig; dennoch kann ich das nicht beweisen. Habe ich recht? Können Sie sie als gleichwertig beweisen?

cc.complexity-theory interactive-proofs Unglaublich
quelle
2
Sie sollten auch überlegen, ob Sie sich auf "öffentliche" oder "private" Münzen beziehen. In der öffentlichen Münzeinstellung kennen sowohl Prüfer als auch Prüfer die Ergebnisse der zufälligen Auswahl, und bei privaten Münzen kennt der Prüfer die zufälligen Entscheidungen des Prüfers nicht. In diesem letzteren Fall kümmern Sie sich nur darum, was der Prüfer tut, ohne den Prüfer anzusehen, da der Prüfer die zufälligen Münzwürfe einfach nicht kennt.
Marcos Villagra
@Marcos: Sehen Sie sich die ursprüngliche Definition interaktiver Proofs an, bei der es sich um "private" Münzen handelt. Der letzte Satz der ersten Spalte auf Seite 293, der unterstrichen ist, besagt, dass "die Wahrscheinlichkeiten nur über Bs eigene Münzwürfe genommen werden". (Hier ist B der Prüfer.) Andererseits ermöglicht die Journalversion des oben genannten Papiers, dass die Wahrscheinlichkeiten über die Münzwürfe beider Parteien übernommen werden. Dies könnte die Quelle der Verwirrung sein, oder?
MS Dousti
@Sadeq: Ich verstehe, ich wusste nichts über diesen Unterschied zwischen der Journal- und der Konferenzversion. Für private Münzen sehe ich jedoch keinen Sinn darin, die Münzwürfe der Prüfer zu berücksichtigen, da er beschließen könnte, dem Prüfer nichts davon zu erzählen. Der Prüfer ist für die Entscheidung über die Annahme oder Ablehnung verantwortlich und weiß möglicherweise nicht, was der Prüfer tut.
Marcos Villagra
1
@Marcos: Sie haben Recht, aber die gleiche Argumentation gilt für öffentliche Münzprüfungen. da in diesen Systemen die Münzwürfe des Prüfers immer noch privat sind (nur die Münzen des Prüfers sind öffentlich). Im Allgemeinen kann man einen deterministischen Beweis betrachten: Da der Beweis allmächtig ist, braucht er keine Zufälligkeit und kann die optimale Antwort deterministisch wählen. Diese Art von Argumentation funktioniert jedoch nicht, wenn wir Systeme ohne Wissen betrachten, in denen die Strategie des Prüfers probabilistisch sein sollte (andernfalls würde sein Wissen auslaufen).
MS Dousti
2
(Fortsetzung) Wenn der Prüfer randomisiert ist, besteht meiner Meinung nach die richtige Formulierung darin, die Wahrscheinlichkeit über beide Münzwürfe des Prüfers und des Prüfers zu berechnen: Während, wie Marcos sagte, der Prüfer für die endgültige Entscheidung verantwortlich ist, ist ihre Entscheidung gemacht (unter anderem) basierend auf den Nachrichten, die vom Prüfer kommen. Angesichts der Tatsache, dass der Prüfer zufällig ausgewählt ist, wirken sich seine Münzwürfe sicherlich auf die von ihm gesendeten Nachrichten aus. Daher beeinflussen die Münzwürfe des Prüfers die Akzeptanzwahrscheinlichkeit. Habe ich recht?
MS Dousti

Antworten:

6

Der Prüfer ist "allmächtig und verfügt über unbegrenzte Rechenressourcen", sodass keine zufälligen Bits erforderlich sind. Somit ist die einzige Zufälligkeit die Zufälligkeit des Verifizierers.

Wenn der Prüfer zufällige Bits verwendet, sollte er diese durch die zufällige Bitfolge ersetzen, die den Prüfer am wahrscheinlichsten akzeptiert (dies gilt sowohl für den ehrlichen als auch für den unehrlichen Prüfer). Darüber hinaus kann der Prüfer diese optimale Bitfolge bestimmen, da der Prüfer "allmächtig" ist.

Tyson Williams
quelle
1
Wie ich oben in einem Kommentar sagte, gilt dies nur, wenn Sie nur interaktive Beweise betrachten. Ganz anders sieht es jedoch aus, wenn Sie andere Eigenschaften berücksichtigen, z. B. "Null Wissen", das natürlich mit interaktiven Beweisen verbunden ist.
MS Dousti
1
Fortsetzung: Insbesondere hat Oren Folgendes bewiesen: "... Unter der Definition der Hilfseingabe von Nullwissen ist die Zufälligkeit des Prüfers wesentlich für die Nicht-Trivialität von Null-Wissensbeweis-Systemen. Mit anderen Worten, jede Sprache das über ein wissensfreies Beweissicherungssystem mit Hilfseingabe verfügt, bei dem der Prüfer für BPP deterministisch ist. " ( Weitere Informationen finden Sie in Abschnitt 4.5 von Oren .) Daher können Sie nicht immer davon ausgehen, dass P deterministisch ist.
MS Dousti