Beweis Komplexität eines Beweises oder Disproofs von P = NP

Wurde die Beweiskomplexität einer Lösung für das P = NP-Problem untersucht? Wenn nicht, wäre es angesichts des Mangels an Fortschritten in Bezug auf das Problem unvernünftig anzunehmen, dass jeder Beweis, der das P = NP-Problem löst, eine überpolynomielle Anzahl von Schritten erfordert?

Es ist bekannt, dass jeder Beweis von Untergrenzen von Superpolynomkreisen (die etwas stärkere Aussagen als ) in schwachen Beweissystemen wie der Auflösung Superpolynombeweise, sogar Beweise mit exponentieller Größe, erfordert. Dies auf stärkere Beweissysteme zu verallgemeinern, ist ein bekanntes offenes Problem.$P\neq NP$

Siehe Abschnitt 5 dieser Umfrage von A. Rasborow, wo diese Dinge gezeigt werden.

Beweiskomplexität ist nur dann sinnvoll, wenn abhängig von einem Parameter eine Folge von Anweisungen vorliegt . Zum Beispiel kann der Satz P H P n Zustände (formlos) , dass es keine Bijektion ist [ n + 1 ] → [ n ] . Diese Satzfolge ist für bestimmte Satzbeweissysteme schwierig.$n$$\mathsf{PHP}_n$$[n+1] \to [n]$

Die Anweisung ist eine einzelne Anweisung, sodass Sie die Beweiskomplexität nicht direkt anwenden können. Die folgende Abfolge von Anweisungen ist jedoch für bestimmte Funktionen s ( n ) sinnvoll : "Es gibt keine Schaltung der Größe s ( n ) , die SAT für Instanzen der Länge n korrekt löst ". Dies wurde in der Literatur beispielsweise von Rasborow (der die Einstellung einer einheitlichen Beweiskomplexität, dh einer beschränkten Arithmetik, in Betracht zog) in Betracht gezogen.$\mathsf{P} \neq \mathsf{NP}$$s(n)$$s(n)$$n$

Wir haben 3 Fälle:

• Es gibt einen Beweis dafür , dass . Dann gibt es einen Algorithmus, der das Problem "Geben Sie einen Beweis aus, dass P = N P " ist und in O ( 1 ) -Zeit abläuft . Es codiert den Proof in der Turing-Maschine selbst hart und gibt ihn aus. Es läuft in der gleichen Zeit, unabhängig von seiner Eingabe.$P = NP$$P=NP$$O(1)$

• In ähnlicher Weise , wenn es existiert ein Beweis , dass , als wir einen Algorithmus schreiben kann diesen Nachweis in Emittieren O ( 1 ) Zeit.$P\neq NP$$O(1)$

• $O(\infty)$

Nur weil wir keinen Beweis gefunden haben, heißt das nicht, dass er nicht existiert, und die Komplexitätsklassen werden in Bezug auf das, was existiert, definiert.

$P=NP$

Was wir wissen, ist, dass das Problem "Nehmen Sie eine Aussage in der Prädikatenlogik und stellen Sie fest, ob es einen Beweis dafür gibt" im Allgemeinen nicht zu entscheiden ist. Es gibt also keine generischen Proof-Generierungsverfahren, in die wir P vs NP einstecken können, die garantiert ein Ergebnis liefern.

Wenn P = NP dann alle müssen Sie tun , ist eine Polynomialzeitalgorithmus zur Lösung einige NP-vollständiges Problem zu schaffen, und beweisen , dass es in der Tat Polynom ist (was schwierig sein könnte, zum Beispiel der Simplex - Algorithmus in der Regel sehr schnell läuft , aber beweisen , dass es läuft schnell scheint unglaublich schwierig).

$n^{100}$