Ist

10

Ich konnte in der Literatur keine Aussage zu MA und NPRP ; Hinweise wären willkommen.

Ich glaube, sie sind gleich:

  • MANPRP : DieNP Maschine errät Merlins Saite, und dasRP Orakel überprüft die Saite wie Arthur.

  • : Merlin schätzt die akzeptierende Berechnung der N P- Maschine, einschließlich aller Anrufe, sowie die Ergebnisse dieser Anrufe an das R P- Orakel. Arthur dann überprüftdass die Berechnung gültigund dass alle die vermuteten Ergebnisse der Anrufe an den R P Orakel korrekt waren. Er verwendet Verstärkungs- und Vereinigungsgrenzen, um die gesamte Fehlerwahrscheinlichkeit zu begrenzen.NPRPMANPRPRP

Ist das richtig?

Joel
quelle
6
Es hängt davon ab, wie Sie diese Notationen definieren. Wenn Sie diese Komplexitätsklassen jedoch als Sprachklassen definieren, ist Ihre Argumentation im ersten Aufzählungszeichen fehlerhaft. Siehe ∃BPP im Complexity Zoo und die darin enthaltene Referenz ( Fenner, Fortnow, Kurtz und Li 2003 ).
Tsuyoshi Ito
Beeindruckend! Vielen Dank Tsuyoshi, dies ist ein sehr subtiler Punkt, und tatsächlich ist mein erster Punkt falsch.
Joel
@ TsuyoshiIto: Machen Sie das eine Antwort?
Joshua Grochow
@Joshua: Ich poste oft eine Teilantwort als Kommentar, wenn ich sie aus irgendeinem Grund nicht als meine Antwort posten möchte. Jeder kann meinen Kommentar als Antwort erneut veröffentlichen, wenn er dies möchte. Ich fühle mich nicht verpflichtet, etwas als Antwort zu posten, nur weil ich es als Kommentar gepostet habe.
Tsuyoshi Ito
2
@ TsuyoshiIto: Okay, ich habe es zu einer CW-Antwort erweitert.
Emil Jeřábek

Antworten:

9

In der ersten Kugel brauchen wir das Orakel, um zu antworten

  • 1

  • 1/2

MANPpromiseRP

Emil Jeřábek
quelle
Sie mussten diese Antwort nicht zu einem Community-Wiki machen, obwohl die Wahl bei Ihnen lag.
Tsuyoshi Ito