in Bezug auf

Das probabilistische Beweissystem wird allgemein als Einschränkung von , wobei Arthur nur Zufallsbits verwenden und nur untersuchen kann Bits des von Merlin gesendeten Proof-Zertifikats (siehe http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).$\mathcal{PCP}[f(n),g(n)]$$\mathcal{MA}$$f(n)$$g(n)$

1990 haben Babai, Fortnow und Lund jedoch bewiesen, dass , es ist also nicht gerade eine Einschränkung. Was sind die Parameter ( ) für welche ?$\mathcal{PCP}[poly(n), poly(n)] = \mathcal{NEXP}$$f(n),g(n)$$\mathcal{PCP}[f(n), g(n)] = \mathcal{MA}$

Wenn Sie die Definition von MA in Bezug auf PCP neu formulieren möchten, benötigen Sie einen weiteren Parameter für PCP, nämlich die Prooflänge. MA ist eindeutig dasselbe wie PCP, mit polynomischer Zufälligkeit, polynomischen Abfragen und Beweisen mit polynomischer Länge. Normalerweise ist die Prooflänge in PCP nicht beschränkt (dh sie ist nur implizit durch Zufälligkeiten und Abfragen begrenzt), dies reicht jedoch nicht aus, um die Definition von MA neu zu formulieren.

Wenn Sie nach einer Charakterisierung der Form MA = PCP ( q ( n ), r ( n )) suchen , die nicht nur die Neuformulierung der Definition von MA ist, dann denke ich, dass eine solche Charakterisierung nicht bekannt ist.

Unter der Annahme der Härte, dass die Komplexitätsklasse Schaltkreise exponentieller Größe erfordert, reicht es aus, M A zu derandomisieren , so dass M A = N P ist . Tatsächlich soll die Derandomisierung zeigen, dass B P P = P ist (siehe Impagliazzo-Wigderson oder Sudan-Trevisan-Vadhan). Aber da in M A die Verifizierer a B P P Maschine, können wir es mit einer deterministischen Maschine ersetzen.$E = DTIME(2^{O(n)})$$MA$$MA = NP$$BPP = P$$MA$$BPP$

Modulo dieser Härteannahme sollte also genau die gleiche PCP-Charakterisierung wie N P haben . Die Komplexitätsgemeinschaft scheint fest davon überzeugt zu sein, dass die Annahme der Härte ebenfalls zutrifft.$MA$$NP$

Bearbeiten: Vielleicht möchten Sie sich auch die Masterarbeit von Andy Drucker ansehen: "Eine PCP-Charakterisierung von ": http://eccc.hpi-web.de/report/2010/019/ .$AM$

Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf

Sudan-Trevisan-Vadhan: http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps

Tsuyoshi Ito beantwortete die Frage wörtlich, aber ich wollte etwas über die Semantik von MA und PCP und deren Unterschiede sagen.

MA ist die probabilistische Version von NP, dh der Verifizierer kann auch mehrere zufällige Bits verwenden.

In PCP können wir uns auf die "Zufälligkeit" des Verifizierers beziehen, aber normalerweise ist die Zufälligkeit in der Laufzeit des Verifizierers logarithmisch, dh der Verifizierer hätte alle möglichen zufälligen Zeichenfolgen selbst ausprobieren können. Mit anderen Worten, diese "Zufälligkeit" verschafft dem Prüfer im Gegensatz zu MA keine Rechenleistung.

[Wofür ist diese "Zufälligkeit" gut? Der Punkt von PCP ist, dass für die probabilistische Verifikation ein einziger Test - mit einer konstanten Anzahl von Anfragen zum Beweis - ausreicht.]

Nachtrag (nach Tsuyoshi): In PCP-Charakterisierungen von NP kann die Laufzeit des Verifizierers polylogarithmiert werden, und in Charakterisierungen von NEXP ist die Laufzeit des Verifizierers ebenfalls polynomisch. Nichtsdestotrotz wird die Zufälligkeit in PCP-Konstruktionen in der Regel nur verwendet, um einen Test auszuwählen (bei Charakterisierungen von NP aus Poly-Many-Tests und bei Charakterisierungen von NEXP aus Exponential-Many-Tests) und nicht um bei der Berechnung zu helfen. Darüber hinaus hat in MA der Beweis eine Polynomgröße, während in Charakterisierungen von NEXP der Beweis eine Exponentialgröße hat.