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

15

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?

Tony Johnson
quelle
18
Vielleicht verstehe ich Ihre Frage nicht, aber jede Auflösung von P gegen NP wäre ein Beweis mit konstanter Größe, ja?
Kurt Mueller
@ Kurt Müller. Der Beweis erfordert eine superpolynomielle Anzahl von Schritten basierend auf der Anzahl von Symbolen, die zum Codieren des P = NP-Problems erforderlich sind.
Tony Johnson
1
@TonyJohnson Superpolynom in einer Konstanten ist immer noch eine Konstante.
David Richerby

Antworten:

14

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.PNP

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

Jan Johannsen
quelle
24

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.nPHPn[n+1][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.PNPs(n)s(n)n

Yuval Filmus
quelle
5

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=NPP=NPÖ(1)

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

  • Ö()

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.

jmite
quelle
-2

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).

n100

gnasher729
quelle
P=?NP? "
David Richerby
Es gibt auch das (unwahrscheinliche, aber durchaus mögliche) Ergebnis, dass P = NP ist, aber es gibt keinen nachweislich einheitlichen Polynom-Zeit-Algorithmus für z. B. SAT.
Steven Stadnicki