Relativierung in Bezug auf nicht rekursive Orakel

8

In der Arbeit Relativierungen des P =? NP Question , Baker et al. zeigten, dass es relativierte Welten gibt, in denen entweder P = NP oder P ≠ NP gilt. Alle Orakel in ihren Einstellungen waren rekursive Mengen.

In einer anderen Arbeit in Bezug auf ein zufälliges Orakel , P AN P Aco- N P A mit Wahrscheinlichkeit 1APANPAco-NPA1 , haben Bennett und Gill den Begriff zufälliger Orakel vorgebracht, die mit ziemlicher Sicherheit nicht rekursive Mengen sind. (Siehe die Kommentare unten.)

Andere nicht rekursive Relativierungen waren mir nicht bekannt, es sei denn, ich hatte eine (siehe diese Frage und Joshuas Antwort darauf).

Was bedeuten nicht rekursive Relativierungen? Wie nützlich sind sie in der Theorie der strukturellen Komplexität?

MS Dousti
quelle
1
Ich verstehe nicht, was Sie unter "zufälligen Orakeln, die nicht rekursive Mengen sind" verstehen. Meinen Sie damit, dass ein zufälliges Orakel mit Wahrscheinlichkeit 1 nicht rekursiv ist?
Robin Kothari
Ja. Zufällige Orakel werden zufällig aus dem Satz aller Funktionen ausgewählt. Ein zählbar unendlicher Teil dieser Menge ist rekursiv, während ein unzähliger Teil der Menge nicht rekursiv ist. Somit definiert das zufällige Orakel mit Wahrscheinlichkeit 1 eine nicht rekursive Funktion.
MS Dousti

Antworten:

8

(1) Lance Fortnow und Scott Aaronson (Abschnitt 1.3) diskutieren gut über die Rolle von Orakeln / Relativierung im Allgemeinen, und ich glaube, dass die meisten, wenn nicht alle ihrer Kommentare gültig bleiben, unabhängig davon, ob das Orakel berechenbar ist oder nicht.

Wenn man Orakeltrennungen als Abfragen der Komplexität von Abfragen betrachtet (eine der Ansichten in Aaronsons Artikel), ergibt ein nicht berechenbares Orakel eine Trennung der Komplexität von Abfragen, bei der die abgefragte Funktion nicht berechenbar ist, was bedeutet, dass die abgefragte Funktion wahrscheinlich ist ist in der realen Welt nicht entstanden. Dennoch scheint es immer noch ein potenziell guter Leitfaden für die Forschung zu sein.

(2) Aus der Sicht des Papiers von Arora, Impagliazzo und Vazirani würde ich sagen, dass nicht berechenbare Orakel weit außerhalb des Bereichs der "realen Welt" der Berechnung liegen.

(3) Wenn wir die "Rechenwelt relativ zu einem Orakel" einfach als ein anderes Berechnungsmodell betrachten, dann sind die berechenbaren Mengen in diesem Modell relativ zu einem berechenbaren Orakel natürlich dieselben wie das Standardmodell, während sie relativ zu einem Nichtmodell sind -computable oracle, es gibt "berechenbare" Mengen, die im Standardmodell nicht berechenbar sind. (Dies ist völlig trivial - es ist meistens ein philosophischer Standpunkt.)

RR

Joshua Grochow
quelle
13

Ich kann nicht widerstehen, einen Stecker für einige aktuelle Ergebnisse einzustecken, was darauf hinweist, dass es interessant sein kann, die Berechnung in Bezug auf die (nicht berechenbare) Menge von Kolmogorov-Zufallszeichenfolgen in Betracht zu ziehen.

RxK(x)|x|URUUKK(x)O(1)

BPPRPSPACEPRNPR

PSPACERUUPSPACER

NPRUU NEXP

Eric Allender
quelle
Ich denke, Eric Referenz ist falsch, ich denke er wollte dieses Papier eccc.uni-trier.de/report/2010/139 anstelle von eccc.uni-trier.de/report/2010/138 verlinken
Sebastian Ben Daniel