Wie kann ich zeigen, dass der Cook-Levin-Satz nicht relativiert?

7

Das Folgende ist eine Übung, an der ich festhalte (Quelle: Sanjeev Arora und Boaz Barak; es sind keine Hausaufgaben):

Zeigen Sie, dass es ein Orakel gibt Aund eine Sprache so dass nicht auf 3SAT polynomialzeitreduzierbar ist, selbst wenn der Maschine, die die Reduktion berechnet, Zugriff gewährt wirdLNPALA .


Was ich versuchte, war, als das Orakel zu nehmen , um das Problem zu stoppen, und . Mit dieser Zuordnung stelle ich sicher, dass und nicht auf 3SAT polynomreduzierbar sind, wenn der Maschine, die die Reduktion durchführt, kein Orakel zur Verfügung gestellt wird. Obwohl ich zum Zuordnen einer Instanz Zeichenfolgen durchsuchen müsste, selbst wenn der Reduktionsmaschine ein Orakel zur Verfügung gestellt wird. Dies scheint jedoch in diesem Fall kein Beweis für das Fehlen einer Polynomreduktion zu sein.AL={1n|M,ws.t.|M,w|=n and Turing machine M halts on w}

LNPAL1n2n

Gibt es eine Möglichkeit, dies anhand des gleichen Beispiels zu beweisen? Gibt es ein einfacheres Beispiel?

Sashas
quelle
Auch hier: cs.stackexchange.com/questions/37749/… .
Yuval Filmus
ist das nicht fast die gleiche Frage wie Baker Gill Solovay 1975 ?
vzn

Antworten:

8

Bitte beziehen Sie sich auf Relativiert der Cook-Levin-Satz? .

Siehe auch Arora, Implagiazo und Vazirani Papier: Relativierung gegen Nonrelativizing Techniken: Die Rolle der lokalen Überprüfbarkeit .

In der Arbeit von Baker, Gill und Solovay (BGS) über Relativierungen des P =? NP-Frage (SIAM Journal on Computing, 4 (4): 431–442, Dezember 1975) geben sie eine SpracheB und UB so dass UBNPB und UBPBund beweist damit, dass es Orakel gibt B für welche PBNPB.

Wir werden das ändern UB und B zu UB und B so dass wir eine neue Sprache erhalten, die nicht auf 3SAT reduziert werden kann, selbst wenn verfügbar ist B als Orakel.

Nehmen wir zunächst an, wir können jeden auffüllen 3SAT Boolesche Instanz ϕ zu ϕ mit einigen zusätzlichen Dummy-3CNF-Ausdrücken, so dass |ϕ| ist seltsam und sie sind gleichwertig, dh ϕ ist erfüllbar wenn ϕist zufriedenstellend. Wir können es schaffenn+O(1) Zeit und mit O(1) Auffüllen, aber selbst wenn es Polynomzeit und zusätzliches Polynomauffüllen benötigt, spielt es keine Rolle.

Jetzt müssen wir das kombinieren B und 3SAT zu B irgendwie so, dass der BGS-Satz immer noch gilt, aber zusätzlich 3SATPB. Also machen wir so etwas wie das Folgende.

UB={1n  |  xB, so dass |x|=12n} und

B=Bconstructed {ϕ  |  ϕ3SAT und |ϕ| ist ungerade }.

Jetzt werden wir konstruieren Bconstructed nach dem Satz so, dass wenn die deterministische Maschine MiB zur Eingabe 1n (n wird wie im Satz bestimmt) fragt das Orakel B Eine Abfrage von ungerader Länge prüfen wir, ob sie vorhanden ist 3SATund antworte richtig, aber wenn es eine Abfrage von gleicher Länge fragt, gehen wir gemäß der Konstruktion vor, das heißt, wir antworten richtig, wenn es bereits in der Tabelle ist, andernfalls antworten wir jedes Mal mit Nein. Dann laufen wir da für1n Wir drehen die Antworten um 2n Länge so dass MiB entscheidet nicht UB.

Wir können dies ähnlich wie im BGS-Theorem beweisen B und UB auch haben wir UBNPB und UBPB.

UBNPBist leicht zu beweisen. Wir konstruieren eine nicht deterministische Turingmaschine, die zur Eingabe dient1n Erstellt nicht deterministische Zweige, für die ausgeführt wird 2n Schritte, um eine andere zu generieren 2n-Länge String und fragt dann Orakel B wenn die 2n-Länge Zeichenfolge ist in Bund wenn die Antwort ja ist, akzeptiert sie 1n sonst lehnt es ab 1n. Diese Konstruktion zeigt dasUBNPB.

UBPBkann mit Hilfe des Diagonalisierungsarguments bewiesen werden. Grundsätzlich unterscheidet es sich von jedemL(MiB) für jede Orakel Turing Maschine, die haben Bals Orakel. Das liegt daran, wie wir konstruierenBconstructed.

Nun werden wir im Widerspruch beweisen, dass es keine Reduktion von gibt UB zu 3SAT auch mit der Verfügbarkeit von Orakel B.

Angenommen, es gibt eine Reduzierung mit Orakel Bdh UBPB3SAT.

Das heißt, wir können eine Zeichenfolge des Formulars reduzieren 1n zu einer 3SAT-Instanz ϕ unter Verwendung einer deterministischen Polynom-Zeit-Maschine, die verwendet B als Orakel.

Wir können nun ein deterministisches TM beschreiben MB welches Saiten entscheiden wird UB in Polynomzeit mit Bals Orakel. Zuerst reduziert diese Maschine die Eingabe1n zu einer 3SAT-Instanz ϕ mit Bals Orakel. Dies kann getan werden, weil wir die oben genannte Reduzierung haben. Dann wennϕ ist keine ungerade Länge MB wird es auffüllen zu machen ϕDas ist ungerade Länge. Als nächstes wird es dies gebenϕ zum Orakel Bund bekomme die Antwort ja / nein. Es wird akzeptiert, wenn die Antwort ja ist, und ablehnen, wenn die Antwort nein ist.

Diese Maschine ist deterministisch polynomisch und verwendet Orakel B.

Damit haben wir das bewiesen UBPBein Widerspruch .

Deshalb UBPB3SAT.

Shreesh
quelle
Wie ist LPBmöglich ? Ich würde die Mitgliedschaft von entscheidenLin Polynomzeit und ordnen Sie es abhängig von der Zugehörigkeit der Zeichenfolge einer kleinen SAT-Formel zu. Vermisse ich etwas
Sashas
Der erste Link gibt keinen Beweis. Könnten Sie irgendwelche Hinweise geben, warum diese SpracheUBIn Sanjeev Arora und Barak wird die Polynomzeit nicht auf 3SAT reduziert. Auch der zweite Link funktioniert nicht.
Sashas
Wie geht das? UBNP? Läuft nicht jeder Zweig einer nicht deterministischen Turingmaschine für 2 ^ n?
Sashas
1
Beachten Sie, dass ich neu definiert habe UB. EbenfallsUBNPB. Es darf nicht (nicht !!) dazu gehörenNP.
Shreesh
1
Jeder Zweig läuft für 2n Schritte, um eine andere zu generieren 2n-Länge String und fragt dann Orakel, ob es in ist Bund wenn die Antwort ja ist, akzeptiert sie sonst, lehnt sie ab 1n.
Shreesh