Warum ist die Relativierung eine Barriere?

Question

Als ich ihm erklärte, dass die Baker-Gill-Solovay Beweis, dass es ein Orakel mit, die können wir haben, $\mathsf{P} = \mathsf{NP}$, und ein Orakel mit, das wir können $\mathsf{P} eq \mathsf{NP}$, um einen Freund, eine Frage kam auf, warum solche Techniken sind ungeeignet für den Nachweis der $\mathsf{P} eq \mathsf{NP}$ - problem, und ich konnte nicht geben Sie eine befriedigende Antwort.

Um es konkret, wenn ich eine Methode zu beweisen $\mathsf{P} eq \mathsf{NP}$ und wenn ich könnte, konstruieren, Orakel, um eine situation wie oben geschehen, warum macht es meine Methode unwirksam?

Jede exposition/Gedanken zu diesem Thema?

Answer 1

Um es konkret, wenn ich eine Methode zu beweisen, P≠NP, und wenn ich bauen konnten, Orakel, um eine situation wie oben geschehen, warum macht es meine Methode unwirksam?

Beachten Sie, dass der letztere, "wenn" ist nicht ein Zustand, weil Baker, Gill und Solovay bereits gebaut wie ein Orakel.Es ist nur eine mathematische Wahrheit ist, dass (1) es gibt ein Orakel, relativ zu dem P=NP, und dass (2) es gibt ein Orakel, relativ zu dem P≠NP.

Dies bedeutet, dass, wenn Sie einen Ansatz, um zu beweisen, P≠NP und den gleichen Nachweis auch beweisen ein stärkeres Ergebnis “P^Ein≠NP^Ein für alle Orakel Ein"dann ist Ihr Ansatz ist zum scheitern verurteilt, weil es im Widerspruch zu (1).

In anderen Worten, es gibt einige grundlegende Unterschied zwischen Beweis von P≠NP und beweisen, z.B.die Zeit-Hierarchie-theorem, weil der Nachweis der letzteren nur verwendet diagonalization und ist gleichermaßen anwendbar auf alle relativierte Welt.

Natürlich, dies bedeutet nicht, dass es keinen Beweis für P≠NP.Solch ein Nachweis (wenn vorhanden) müssen scheitern, um zu beweisen, desto stärker das Ergebnis oben erwähnt.In anderen Worten, ein Teil des Beweises ist zu unterscheiden zwischen der nonrelativizing Welt aus beliebigen relativiert Welten.

Answer 2

Es gibt bereits gute Antworten, aber ich möchte ein paar kleine Punkte hinzufügen.

Angenommen, wir haben eine Technik, um Probleme zu lösen, z. B. Diagonalisierung. Angenommen, wir möchten zeigen, dass die Technik ein bestimmtes Problem nicht lösen kann, z. $ mathsf {p} $ vs. $ mathsf {np} $. Wie kann das zeigen?

Beachten Sie, dass eine Technik wie Diagonalisierung hier kein formales Konzept ist (obwohl wir sie so machen können). Darüber hinaus bedeutet die Tatsache, dass die Technik das Problem an sich nicht lösen kann, nicht, dass es nicht nützlich ist, das Problem zu lösen. Wir können es möglicherweise ändern und/oder mit anderen Techniken kombinieren, um das Problem zu lösen.

Kommen wir nun zur Frage zurück. Eine Möglichkeit zu zeigen, dass eine Technik kein bestimmtes Problem lösen kann, besteht darin, zu zeigen, dass sie auch in einem anderen Rahmen für die Lösung einer anderen Frage funktionieren würde, und die Antwort, die wir in diesem Fall bekommen würden, wäre falsch. Das passiert hier. Wenn die Diagonalisierung $ mathsf {np} $ von $ mathsf {p} $ trennen könnte $ A $. Wir wissen jedoch, dass es ein Orakel gibt, so dass dies falsch ist (nimm ein $ mathsf {pSpace} $-Vollständiges Problem als Orakel). Die Diagonalisierung kann also nicht $ mathsf {np} $ von $ mathsf {p} $ trennen.

Der wesentliche Punkt in diesem Argument ist eine Art Art von Übertragungsprinzip:

Wir können ein Diagonalisierungsargument für TMS ohne Orakel mit Orakel übertragen.

Dies ist hier möglich, da Diagonalisierungsargumente auf Simulation Darüber hinaus hängt die Simulation nicht von den Interna von Maschinen ab, sondern nur von den endgültigen Antworten dieser Simulationen. Diese Art von Diagonalisierung wird als bezeichnet als einfache Diagonalisierung. In einer Simulation spielt es keine Rolle, wie die Maschine funktioniert. Wir kümmern uns nur um die endgültige Antwort der Maschine. Das Hinzufügen eines Orakels ändert dies nicht, sodass die Simulation und das Argument auch im Rahmen, in dem wir Orakel haben, funktioniert.

Formal können wir uns ein Diagonalisierungsargument als Funktion einer Klasse von Maschinen (z. B. $ mathsf {p} $) bis zu Instanzen vorstellen, die zeigen, dass die Maschine ein Problem nicht lösen kann (z. B. $ sat $). Diese Gegenbeispielfunktion ist die Diagonalisierungsfunktion. Eine Diagonalisierung ist einfach, wenn die von ihnen angegebenen Gegenbeispiele nicht von den Interna der Maschinen abhängen. Wenn zwei Polynomzeit -DTMs dieselbe Sprache haben, dann ist das Gegenbeispiel, das zeigt, dass sie nicht durch die Diagonalisierungsfunktion gegeben werden können.

Sie fragen sich vielleicht, ob dies eine große Einschränkung ist? Warum sollte das Gegenbeispiel von der internen Struktur der Maschine abhängen? Können wir Trennungen mithilfe der Diagonalisierung beweisen, die mit einer einfachen Diagonalisierung nicht nachgewiesen werden können? Die Antwort ist ja. Tatsächlich zeigt Kozen in seinem 1978er Papier "Indexierung subrecursive Klassen" (3 Jahre nach dem BGS -Ergebnis), dass $ mathsf {np} $ von $ mathsf {p} $ getrennt werden kann . Und in der Praxis wurden solche Argumente gefunden. Zum Beispiel verwenden Fortnow und Van Melkebeeks Zeitraum unter den unteren Bogen für SAT (2000) eine Technik genannt Indirekte Diagonalisierung Das gibt eine nicht-einfache Diagonalisierung.

Ist die Behauptung also, dass die Diagonalisierung $ mathsf {p} $ vs. $ mathsf {np} $ falsch lösen kann? Nun, im Allgemeinen, was Experten mit Diagonalisierung meinen, ist hier einfache Diagonalisierung Und dafür gibt es einen guten Grund.

Die allgemeinen Diagonalisierungsargumente sind so allgemein, dass es nicht wirklich sinnvoll ist, sie als Technik zu bezeichnen. Kann eine Funktion in der größeren Klasse nicht im kleineren auswählen. Nehmen Sie eine Aufzählung der Maschinen in der kleineren Klasse. Sei $ M $ irgendwelche Maschinen in der Aufzählung. Wir müssen das Gegenbeispiel für M $ definieren. Aber wir wissen bereits, dass $ M $ das Problem nicht lösen kann, also da existiert Wenn Sie dies zeigen, definieren Sie den Wert der Diagonalisierungsfunktion auf $ m $, um diese Instanz zu sein. Dies ist die große Ansicht mit großem Bild, wenn Sie die Details sehen möchten, die das Papier von Kozen überprüfen möchten.

Sommerlich:

• Wenn Experten sagen, "Diagonalisierung kann nicht $ mathsf {p} $ vs. $ mathsf {np} $" lösen "Was sie meinen, ist"einfach Die Diagonalisierung kann nicht $ mathsf {p} $ vs. $ mathsf {np} $ "lösen" nicht der allgemeine.
• Der Grund, warum eine einfache Diagonalisierung $ mathsf {np} $ von $ mathsf {p} $ nicht trennen kann, ist, dass sie mit Oraklern auf das Gerüst überträgt .
• Der Grund, warum diese Übertragung von Orakel ohne Framework mit Oracles funktioniert, ist, dass eine einfache Diagonalisierung auf der Schwarzbox-Simulation von TMS basiert und keine Rolle, wie Maschinen funktionieren, ob ein Orakel oder nicht.

Zwei gute Papiere, um mehr über Diagonalisierung zu erfahren, sind

• Lance Fortnows Vermessungspapier "Diagonalisierung", 2001 und
• Russell Impagliazzo, Valentine Kabanets und Antonina Kolokolovas Papier "Ein axiomatischer Ansatz zur Algebisierung", 2009. (Beachten Sie, dass Algebraisierung ist eine Erweiterung von einfache Diagonalisierung.)

Answer 3

Sei $ mathhrm {a} $ und $ mathrm {b} $ zwei Komplexitätsklassen. Eine Trennung ($ mathhrm {a} neq mathrm {b} $) oder ein Zusammenbruch ($ mathrm {a} = mathrm {b} $) soll sich relativieren, wenn für alle Orakles $ mathrm {o} $ relativieren soll Wir haben $ mathhrm {a}^ mathrm {o} neq mathhrm {b}^ mathrm {o} $ oder $ mathrm {a}^ mathrm {o} = mathrm {b}^ mathrm {O} $ jeweils. Der Baker-Gill-Solovay-Beweis sagt uns, dass $ P = NP $ oder $ P neq np $ nicht relativiert.

Warum ist das ein Problem? Als dieser Beweis herauskam, wurde die Mehrheit der Techniken und Tricks, von denen wir wussten, dass sie die Komplexitätsklassen „relativieren“, indem sie in Bezug auf irgendein Orakel arbeiten. Zum Beispiel der Zeithierarchie -Theorem (sowie der Raum- und nicht -deterministische Versionen davon) "relativieren" irgendein Orakel.

Wenn eine Technik oder ein Trick unabhängig davon, ob ein Orakel vorhanden ist, kann sie möglicherweise nicht nach dem obigen Argument $ p = np $ oder $ p neq np $ beweisen. Dies bedeutet, dass eine große Anzahl von Tricks und Techniken, von denen wir wissen, dass sie an diesem Problem nicht arbeiten (oder in der Tat viele offene Probleme). Sie können es auch als Hausarzt für alle angeblichen $ p neq np $ beweisen: Überprüfen Sie, ob die Idee in Gegenwart eines $ mathrm {pspace} $ - vollständiges Orakel nicht hält - wenn es noch funktioniert, dann ist es dann noch ist falsch.