Widerspruchsbeweis für Ungleichheit von P und NP?

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=NP$ $\mathit{SAT} \in P$ $\mathit{SAT} \in TIME(n^k)$ $NP$ $\mathit{SAT}$ $NP \subseteq TIME(n^k)$ $A \in TIME(n^{k+1})$ $TIME(n^k)$ $A$ $P$ $NP$ $P \neq NP$

Stimmt etwas mit meinem Beweis nicht?

complexity-theory time-complexity p-vs-np inverted_index
quelle

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

@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:

Dann ergibt sich das das dann selbst dem folgt . $SAT \in P$ $SAT \in TIME(n^k)$

Sicher.

Aus heutiger Sicht können wir jede Sprache reduzieren $NP$ auf . Daher . $SAT$ $NP \subseteq TIME(n^k)$

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(n^{r(L)})$ $L$ $SAT$ $r(L)$ $k$ $L \in NP$ $r(L) < k$ $P = NP$

Und diese stärkere Aussage steht in der Tat im Widerspruch zum Satz der Zeithierarchie, der uns dies sagt $P$ nicht in kollabieren $TIME(n^k)$ , geschweige denn alle $NP$ .

orlp
quelle

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

Angenommen, $\mathrm{3SAT}\in\mathrm{NTIME}[n^k]$ . Nach der nichtdeterministischen Version des Zeithierarchiesatzes gibt es für jedes $r$ ein Problem $X_r\in\mathrm{NTIME}[n^r]$ , das nicht in $\mathrm{NTIME}[n^{r-1}]$ . Dies ist ein bedingungsloses Ergebnis, das von keiner Annahme wie abhängt $\mathrm{P}\neq\mathrm{NP}$

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

$\mathrm{NP}$ $\mathrm{3SAT}$ $\mathrm{3SAT}\in \mathrm{P}$ $\mathrm{3SAT}\in\mathrm{DTIME}[n^{k'}]$ $k'$ $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k'}]$ $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k''}]$ $k''>k'$

David Richerby
quelle