MIP mit effizienten Testern

17

Es ist bekannt, dass die Gruppe von Sprachen mit interaktiven Beweisen mit zwei Beweisen, in denen der Verifizierer in Polynomialzeit (MIP) läuft, NEXP ist. Aber gibt es Grenzen für die Macht solcher interaktiven Beweise, wenn die Macht der Prüfer eingeschränkt ist? Was ist beispielsweise die Klasse von Sprachen, die interaktive Beweise mit zwei Beweisen und polynomialen Zeitprüfern zulassen?

Genauer gesagt, lassen wir für eine Eingabe x eine beliebige Vorberechnungszeit für die Prüfer zu, aber sobald die Interaktion mit dem Prüfer beginnt, können sie nur noch den Polynomraum (einschließlich der Speicherung der Ergebnisse einer Vorberechnung) und die Polynomzeit verwenden ihre Antworten auf die Frage des Verifizierers zu berechnen. Nehmen wir auch an, dass diese Raum- und Zeitgrenzen ein festes Polynom in der Länge der Fragen sind, die vom Prüfer gesendet werden (anstelle der Länge von x), um eine trivialere Lösung auszuschließen, bei der der Prüfer irgendwie erschöpft wäre Der Raum des Bewohners wird begrenzt, indem er mehr polynomisch Fragen stellt.

Dies ist eindeutig genug für NP. Was ist mit PSPACE? Wenn es nur den begrenzten Raum gäbe, könnten sie es tun, aber was ist mit der begrenzten Zeit? Gibt es interessante Ergebnisse in dieser Richtung?

Ich interessiere mich auch für andere Einschränkungen, die man bei den Prüfern berücksichtigen könnte. Eine davon wäre die Menge an Kommunikationsprüfern, die meines Erachtens im Zusammenhang mit PCPs gründlich untersucht wurde. Was sind die anderen interessanten Einschränkungen?

Thomas
quelle

Antworten:

17

Es hört sich so an, als wäre diese Klasse genau MA. Der Zeuge könnte das Ergebnis einer Vorverarbeitung sein (die polynomial groß ist). Das probabilistische Überprüfungsverfahren würde dann darin bestehen, das Protokoll zu simulieren, einschließlich der mehreren Prüfer (die aufgrund der Ergebnisse der Vorverarbeitung eine Polynomzeit haben).

Russell Impagliazzo

Russell Impagliazzo
quelle
Guter Punkt, danke. Allgemeiner gesagt habe ich mich gefragt, auf welche Weise mehrere Prüfer Sprachen, die außerhalb ihrer Zeitgrenze T (Modulo des Vorverarbeitungsschritts) liegen, einem Mehrfachzeitprüfer nachweisen können, und Ihre Antwort zeigt, dass dies niemals mehr als der entsprechende sein wird MA (T), mit einem T-Zeit-Prüfer. Aber wie verhält es sich mit einer Poly-Time-Verifier-Klasse? Sagen wir, wenn die Prüfer jetzt PSPACE sein dürfen, können sie immer noch NEXP beweisen. Können sie noch eingeschränkter sein und das Gleiche beweisen?
Thomas
2

Wenn die beiden Prüfer auf zwei BQP-Maschinen beschränkt sind, die nicht miteinander kommunizieren, sich aber die Verstrickung teilen, während sich der Prüfer in BPP befindet, können die beiden Prüfer dem klassischen Prüfer mithilfe der Universal Blind Quantum Computation eine beliebige Sprache in BQP prüfen Protokoll von Broadbent, Fitzsimons und Kashefi. Dieses Protokoll wurde von denselben Autoren auch als Baustein verwendet, um QMIP = MIP * anzuzeigen .

Martin Schwarz
quelle
1
Danke Martin, ich wollte meine eigene Arbeit nicht erwähnen.
Joe Fitzsimons