Widerspruchsbeweis für Ungleichheit von P und NP?

10

Ich versuche zu argumentieren, dass N nicht gleich NP ist, indem ich Hierarchiesätze verwende. Dies ist mein Argument, aber als ich es unserem Lehrer und nach Abzug zeigte, sagte er, dass dies problematisch ist, wenn ich keinen zwingenden Grund finde, dies zu akzeptieren.

Wir beginnen mit der Annahme, dass . Dann ergibt sich das das dann selbst dem folgt . Gegenwärtig können wir jede Sprache in auf reduzieren . Daher . Im Gegenteil, der Zeithierarchiesatz besagt, dass es eine Sprache geben sollte , die nicht in . Dies würde uns zu dem Schluss führen, dass in , während es nicht in , was ein Widerspruch zu unserer ersten Annahme ist. Also kamen wir zu dem Schluss, dass .P=NPSATPSATTIME(nk)NPSATNPTIME(nk)ATIME(nk+1)TIME(nk)APNPPNP

Stimmt etwas mit meinem Beweis nicht?

inverted_index
quelle
2
Bitte schreibe so etwas wie $\mathit{SAT}$statt $SAT$. Wie Leslie Lamport in seinem ursprünglichen LaTeX-Buch schrieb, steht letzteres für S mal A mal T.
Oliphaunt - Monica am
Besser noch, benutze die complexity Paket und schreibe einfach \SAT. (Ich denke, das ist auf diesem Stapel jedoch nicht verfügbar.)
Oliphaunt - Monica am
@Oliphaunt Warum nicht eine Bearbeitung vorschlagen, wenn Sie den Beitrag verbessern können? Obwohl ich sagen muss, dass hier der Unterschied (wenn überhaupt) viel subtiler ist, als ich erwarten würde.
Diskrete Eidechse
1
@Discretelizard mache ich oft, aber diesmal war es "zu viel Arbeit" (ich war / bin auf dem Handy). Die Eingabe all dieser $ und \ ist eine schwierige Aufgabe. Ich entschied mich stattdessen zu erziehen. (Diese Entscheidung war möglicherweise nicht ganz rational.)
Oliphaunt - Monica am

Antworten:

55

Dann ergibt sich das das dann selbst dem folgt .SATPSATTIME(nk)

Sicher.

Aus heutiger Sicht können wir jede Sprache reduzieren NP auf . Daher .SATNPTIME(nk)

Nr Polynomial Zeitverkürzungen sind nicht frei. Wir können sagen, dass es Zeit braucht , um die Sprache auf zu reduzieren , wobei der Exponent in der verwendeten Polynomzeitreduktion ist. Hier fällt Ihr Argument auseinander. Es gibt kein endliches so dass wir für alle . Zumindest folgt dies nicht aus und wäre eine viel stärkere Aussage.O(nr(L))LSATr(L)kLNPr(L)<kP=NP

Und diese stärkere Aussage steht in der Tat im Widerspruch zum Satz der Zeithierarchie, der uns dies sagt P nicht in kollabierenTIME(nk) , geschweige denn alleNP .

orlp
quelle
1
Es ist nicht nur die Zeit für die Reduzierung selbst. Sie könnten sich auf ein größeres Problem reduzieren. Wenn ich X in O (n ^ 5) lösen und ein Problem in Y in O (n ^ 6) auf eine O (n ^ 3) -Instanz von X reduzieren kann, dann brauche ich O (n ^ 15) insgesamt.
Gnasher729
Amüsanterweise gilt dieses Argument auch für PTIME-vollständige Probleme, z. B. HORNSAT, das in linearer Zeit lösbar ist (aber nicht alle Probleme in P sind lineare Zeit).
Cody
8

Angenommen, 3SATNTIME[nk] . Nach der nichtdeterministischen Version des Zeithierarchiesatzes gibt es für jedes  r ein Problem XrNTIME[nr] , das nicht in NTIME[nr1] . Dies ist ein bedingungsloses Ergebnis, das von keiner Annahme wie PN abhängtPNP

Wählen Sie ein beliebiges r>k . Angenommen, wir haben eine deterministische Reduktion von Xr auf 3SAT , die in der Zeit nt abläuft  . Es wird eine 3SAT -Instanz mit einer Größe von höchstens nt , die höchstens  zeitlich gelöst werden kann (nt)k=ntk . Nach unserer Wahl von  Xr müssen wir tk>r1 , also t>(r+1)/k . Diese Funktion wächst ohne Bindung an r .

NP3SAT3SATP3SATDTIME[nk]kNPDTIME[nk]NPDTIME[nk]k>k

David Richerby
quelle