Was sind natürliche Beispiele für nicht relativierbare Beweise?

13

Nach meinem Verständnis müsste ein Beweis, dass P = NP oder P ≠ NP ist, nicht relativierbar sein (wie in Orakeln der Rekursionstheorie).

Praktisch alle Beweise scheinen jedoch relativierbar zu sein.

Was sind gute Beispiele für nicht relativierbare Beweise, wie sie ein P = NP / P ≠ NP-Beweis benötigt, die nicht trivial oder erfunden sind?

(Ich bin kein Rekursionstheoretiker, bitte verzeihen Sie das Fehlen von Zitaten.)

[ BEARBEITEN : besserer Mathoverflow Beitrag]

Sai
quelle
6
Um meinen Vorschlag von MO zu kopieren und aus dem Weg zu räumen: Das kanonische Beispiel, das mir bekannt ist, ist der Nachweis von IP = PSPACE, wobei insbesondere die Einbeziehung von PSPACE in IP erfolgt, indem ein interaktiver Nachweis für ein bestimmtes PSPACE gezeigt wird -komplettes Problem, eine nicht relativierbare Technik - bestimmte Probleme relativieren sich nicht.
Steven Stadnicki
5
@AndrejBauer AFAIK, nein, weil es so etwas wie "relativiertes TQBF" nicht gibt - tatsächlich gibt es Orakel mit I P AP S P A C E A , daher kann der Beweis nicht kanonisch relativiert werden. EINichPEINPSPEINCEEIN
Steven Stadnicki
4
@Steven: Relativiertes TBQF kann gebildet werden, indem Orakel-Gates anstelle von nur (Standard-) Logik-Gates zugelassen werden.
3
@RickyDemer Trotzdem interpretiert das Herzstück des Beweises die Formel als ein Polynom niedrigen Grades, das sich nicht durchsetzt, wenn Sie ein einheitlich zufälliges Orakeltor haben.
Yonatan N
1
Das P = & Dgr; NP-Ergebnis bei der Relativierung wird als Baker-Gill-Solovay- Satz von 1975 bezeichnet. Der Beweis kann auch zB in Hopcroft / Ullman gefunden werden . @ richerby / Sai Es gibt keinen Grund für eine Migration, nachdem beide Fragen bereits eingegeben wurden. Beachten Sie auch, dass es anscheinend keine offizielle Cross-Site-Richtlinie für Stack-Exchange zum Crossposting gibt (daher ist eine gewisse Verwirrung verständlich).
vzn

Antworten:

24

Wie Steven Noten, das kanonische Beispiel . Dieser Zusammenbruch relativiert sich nicht in dem Sinne, dass es ein Orakel A gibt , dem I P AP S P A C E A unterliegt . Die Intuition, warum der bekannte Beweis für dieses Ergebnis die Relativierungsbarriere umgeht, ist, dass es eine Arithmetisierung verwendet (Yonatan spielte in einem Kommentar darauf an): ein interaktives Protokoll für das P S P A C EichP=PSPEINCEEINIPAPSPACEAPSPEINCE-komplettes Problem TQBF wird gegeben, indem eine Erweiterung einer quantifizierten Booleschen Formel auf ein Polynom niedrigen Grades über ein geeignet großes Feld betrachtet wird. Wenn wir eine relativierte Boolesche Formel (mit Orakeltoren) erhalten, existiert eine solche Erweiterung nicht.

Es gibt eine Verfeinerung der Relativierungsbarriere - Algebrisierung - aufgrund von Aaronson und Wigderson . Generell reicht die Arithmetisierungstechnik nicht aus, um die Algebrisierungsbarriere zu umgehen. Eine Einbeziehung der Komplexitätsklasse algebriert, wenn für jedes Orakel A und jede Erweiterung ˜ A von A auf Polynome niedrigen Grades über ein endliches Feld C AD giltCDEINEIN~EIN . Eine TrennungCDalgebriert, wenn für alleAund alle Erweiterungen˜A,C ˜ ACEINDEIN~CDEINEIN~ . Aaronson und Wigderson zeigen, dass I P = P S P A C E algebrisiert, viele andere Ergebnisse, einschließlich N P P , jedoch nicht.CEIN~DEINichP=PSPEINCENPP

Ein jüngeres Beispiel für eine Technik , die algebrize Relativieren oder nicht , ist Beweis Ryan Williams , dass . Die Trennung nicht algebrize: es ist ein Oracle A und ein niedriger Grad Verlängerung ~ A , so dass N E X P ~ AA C C A . Intuitiv der Grund , warum der Beweis die Barriere vermeidet , ist , dass es beruht auf der Existenz eines schneller als trivial Erfüllbarkeit Algorithmus für A C CNEXPACCAA~NEXPA~ACCAACCSchaltungen, und der Algorithmus verwendet nicht-relativierende und nicht-algebrierende Eigenschaften solcher Schaltungen. Ryan merkt in dem Artikel an, dass alle bekannten schneller als trivialen Erfüllungsalgorithmen zusammenbrechen, wenn Orakel oder algebraische Erweiterungen von Orakeln hinzugefügt werden.

Es gibt auch einen interessanten Ansatz, um Relativierung durch Logik zu verstehen. In einem alten Manuskript definieren Arora, Impagliazzo und Vazirani ein Axiomensystem so, dass die relativierenden Ergebnisse genau die sind, die sich aus den Axiomen ergeben, während die nicht relativierenden Ergebnisse vom System unabhängig sind. Eine Arbeit von Impagliazzo, Kabanets und Kolokolova macht etwas Ähnliches für die Algebrisierung, indem ein zusätzliches Axiom zu den von Arora, Impagliazzo und Vazirani definierten eingeführt wird. Sie zeigen, dass die meisten bekannten nicht-relativierenden Ergebnisse aus ihren Axiomen resultieren, während P vs NP unter anderem von ihnen unabhängig ist.

Entschuldigung, wenn ich etwas falsch gemacht habe, bin ich kein richtiger Experte.

Sasho Nikolov
quelle
7
Es gibt andere Beispiele für nicht-Relativierung Proofs im Aaronson Wigderson-Papier, wie , MA EXPP / Poly , PromiseMASIZE ( n k ) , usw.NEXPMIPMAEXPP/polyPromiseMASIZE(nk)
Robin Kothari
10

Hier ist eine Liste nicht relativierbarer Beweise:

  1. Der PCP-Satz

  2. Instanzabhängiges Commitment impliziert ein Zero-Knowledge-Protokoll:
    Eine Äquivalenz zwischen Zero Knowledge und Commitments

  3. Es gibt keinen effizienten "virtuellen Black-Box" -Schutz für allgemeine Stromkreise:
    Eine Äquivalenz zwischen null Wissen und Verpflichtungen

  4. PSPACE kann auf die Bewertung eines prägnanten Produkts von reduziert werden : PSPACe übersteht Drei-Bit-EngpässeS5

  5. NEXP hat gegen nicht verwickelte Prüfer minimal-interaktive 2-Beweis-Systeme: Zwei- Beweis
    -Ein-Runden-Beweis-Systeme: ihre Kraft und ihre Probleme

  6. Gegen möglicherweise verwickelte Prüfer verfügt NEXP über interaktivere MIP-Protokolle:
    Ein interaktiver Mehrfachprüfer-Beweis für NEXP-Sound gegen verwickelte Prüfer



  7. Ciπ wenn es nicht möglich wäre, ein Element aus {0,1,2,3, ..., n! -1} in einer ausreichend kleinen Zeitspanne vollkommen gleichmäßig auszuwählen, da eine solche Auswahl die vollkommen gleichmäßige Erzeugung von a ermöglichen würde gerichtete Zyklusdiagrammmatrix oder eine Permutation der Eckpunkte.

Kaveh
quelle
7

Dies ist eine schöne Übersicht über das Gebiet durch einen führenden Experten, der einige der Punkte der anderen bisherigen Antworten zusammenfasst / detailliert und zusätzliche Beispiele enthält.

[1] Die Rolle der Relativierung in der Komplexitätstheorie Fortnow

Mehrere nichtrelativierende Ergebnisse der letzten Zeit im Bereich der interaktiven Beweise haben viele Menschen veranlasst, die Bedeutung der Relativierung zu überdenken. In diesem Artikel untersuchen wir, wie Komplexitätstheoretiker Orakelergebnisse verwenden und missbrauchen. Wir widmen den neuen interaktiven Proofsystemen und Programmprüfergebnissen besondere Aufmerksamkeit und versuchen zu verstehen, warum sie nicht relativieren. Wir geben einige neue Ergebnisse, die uns helfen können, diese Fragen besser zu verstehen.

vzn
quelle
6
+1 Dies ist eine schöne Umfrage, aber es sollte erwähnt werden, dass es den Zustand der Welt bis 1993
Sasho Nikolov
wahr; Es wäre hilfreich, wenn Autoren Daten in ihre Artikel aufnehmen würden. Eine neuere Umfrage wäre ebenfalls hilfreich, das Thema scheint selten untersucht zu werden. Dieser Bereich scheint sich nicht so sehr zu ändern und es ist nicht klar, wie viele neue Ergebnisse seit diesem Datum entstanden sind.
vzn
3
für neue Ergebnisse: Ich denke, seitdem sind einige neue Orakelergebnisse aufgetaucht, die sich auf Quantenkomplexitätsklassen beziehen. Noch wichtiger ist, dass es Entwicklungen in Bezug auf die Bedeutung von Orakelergebnissen gegeben hat: die Algebrisierungsbarriere und Ryans nicht-algebrisierende Beweise aus meiner Antwort, eine verwandte Veröffentlichung cs.sfu.ca/~kabanets/papers/act-full.pdf und möglicherweise Boaz Baraks Arbeit über nicht-Black-Box-Reduktionen bei Krypto.
Sasho Nikolov