Implikationen der Nichtprovabilität von

22

Ich las " Ist P gegen NP formal unabhängig? ", Aber ich wurde verwirrt.

Es ist weit verbreitet in der Komplexitätstheorie glaubt , dass PNP . Meine Frage ist, was ist, wenn dies nicht nachweisbar ist (sagen wir in ZFC ). (Nehmen wir an, wir finden nur heraus, dass PNP unabhängig von ZFC aber keine weiteren Informationen darüber, wie dies bewiesen wird.)

Was bedeutet diese Aussage? Genauer,

Härte

Unter der Annahme , dass die P - Capture die effiziente Algorithmen ( Cobham-Edmonds These ) und PNP , wir beweisen NP-hardness Ergebnisse implizieren , dass sie über die Gegenwart hinaus Reichweite unserer effizienten Algorithmen sind. Wenn wir die Trennung, beweisen NP-hardness bedeutet , dass es kein Polynomialzeitalgorithmus ist. Aber was bedeutet ein Ergebnis bedeutetwenn die Trennung nicht beweisbar ist? Was passiert mit diesen Ergebnissen?NP-hardness

effiziente Algorithmen

Bedeutet die Unbeweisbarkeit der Trennung, dass wir unsere Definition effizienter Algorithmen ändern müssen?

Karthik
quelle
13
Das erste, was Sie fragen müssen, ist: formal unabhängig von was? In der mathematischen Logik gibt es viele Sätze von Axiomen, die von Menschen berücksichtigt wurden. Die Standardeinstellung ist ZFC oder die Zermelo-Fraenkel-Mengen-Theorie mit dem Axiom of Choice. Was es bedeutet, unabhängig von ZFC zu sein, ist, dass weder P = NP noch P! = NP aus diesen Axiomen bewiesen werden können.
Peter Shor
2
Wenn Sie wissen möchten, wie ein Beweis für eine Aussage der Form "ob X vom Axiomatischen System Y unabhängig ist oder nicht" aussieht, warum lesen Sie nicht einfach einige Beispiele? Die Unabhängigkeit des Axioms der Wahl von der Zermelo-Fraenkel-Mengenlehre ist ein berühmtes Beispiel. Ich habe aus Versehen dafür gestimmt, als keine echte Frage abzuschließen, aber ich wollte dafür stimmen, als Thema abzuschließen.
Tsuyoshi Ito
15
Haben Sie die sehr gute und frei verfügbare Arbeit von Scott Aaronson gelesen? "Ist P gegen NP formal unabhängig?" ( scottaaronson.com/papers/pnp.pdf )
Marzio De Biasi
2
Die Frage "Wenn X unabhängig von ZFC ist und wir einige Theoreme der Form X Y haben, was passiert mit diesen Theoremen?" scheint gut gestellt zu sein und ist die Frage, die das OP meiner Meinung nach stellt. Die Antwort scheint zu sein: In einigen Axiomensystemen wie ZFC + X haben wir dann Y-Werte, während wir in ZFC + ¬ X keine Informationen über Y haben. Als solche hätten diese Bedingungssätze immer noch einen gewissen Wert. Tatsächlich hätten sie in dieser Situation mehr Wert, als wenn sich ¬ X als Theorem herausstellen würde. ¬¬
András Salamon
2
Die ZFC-Unprovabilität von P vs NP hätte wahrscheinlich eine viel größere Bedeutung für die Mengenlehre als die Komplexitätstheorie.
David Harris

Antworten:

18

Ihre Frage könnte besser formuliert werden: "Wie würde sich die Komplexitätstheorie auf die Entdeckung eines Beweises auswirken, dass P = NP formal unabhängig von einem starken axiomatischen System ist?"

Es ist ein wenig schwierig, diese Frage abstrakt zu beantworten, dh wenn die Details des Beweises nicht gesehen werden. Wie Aaronson in seiner Arbeit erwähnt, würde der Nachweis der Unabhängigkeit von P = NP radikal neue Ideen erfordern, nicht nur in Bezug auf die Komplexitätstheorie, sondern auch in Bezug auf den Nachweis von Unabhängigkeitserklärungen. Wie können wir die Folgen eines radikalen Durchbruchs vorhersagen, dessen Form wir derzeit nicht einmal erraten können?

Dennoch gibt es einige Beobachtungen, die wir machen können. Im Gefolge des Beweises der Unabhängigkeit der Kontinuumshypothese von ZFC (und später von ZFC + großen Kardinälen) ist eine beträchtliche Anzahl von Personen zu dem Standpunkt gelangt, dass die Kontinuumshypothese weder wahr noch falsch ist . Wir könnten fragen, ob die Leute in ähnlicher Weise zu dem Schluss kommen, dass P = NP nach einem Unabhängigkeitsbeweis "weder wahr noch falsch" ist (aus Gründen der Argumentation nehmen wir an, dass P = NP unabhängig von ZFC + ist, egal wie groß Kardinalaxiom). Ich vermute nicht. Aaronson sagt im Grunde, dass er nicht würde. Goedels 2. Unvollständigkeitssatz hat niemanden, den ich kenne, dazu gebracht zu argumentieren, dass "ZFC konsistent ist" weder wahr noch falsch ist.Aussage, und die meisten Menschen haben eine starke Intuition, dass arithmetische Aussagen - oder zumindest arithmetische Aussagen so einfach wie "P = NP" - entweder wahr oder falsch sein müssen. Ein Unabhängigkeitsbeweis würde nur so interpretiert werden, dass wir keine Möglichkeit haben zu bestimmen, welcher von P = NP und P NP der Fall ist.

Man kann sich auch fragen, ob die Leute diesen Zustand so interpretieren würden, dass sie uns sagen, dass mit unseren Definitionen von P und NP etwas "falsch" ist. Vielleicht sollten wir dann die Grundlagen der Komplexitätstheorie mit neuen Definitionen wiederholen, mit denen man besser arbeiten kann? Ich denke, wir befinden uns derzeit im Bereich wilder und unfruchtbarer Spekulationen, in denen wir versuchen, Brücken zu überqueren, die wir noch nicht erreicht haben, und Dinge zu reparieren, die noch nicht kaputt sind. Darüber hinaus ist nicht einmal klar, dass irgendetwas passieren würdein diesem Szenario "kaputt" sein. Mengenlehre-Theoretiker sind vollkommen glücklich, wenn sie annehmen, dass große Kardinal-Axiome ihnen zusagen. Ebenso könnten Komplexitätstheoretiker in dieser hypothetischen zukünftigen Welt vollkommen glücklich sein, wenn sie Trennungsaxiome annehmen, die sie für wahr halten, auch wenn sie nachweislich nicht beweisbar sind.

Kurz gesagt, aus einem Unabhängigkeitsnachweis von P = NP folgt logischerweise nicht viel . Das Gesicht der Komplexitätstheorie mag sich angesichts eines solch fantastischen Durchbruchs radikal ändern, aber wir müssen nur abwarten, wie der Durchbruch aussieht.

Timothy Chow
quelle
3
@vzn: Ihre Beispiele sind nicht nur "wohl" arithmetisch; sie sind zweifellos arithmetisch. Aber ich bin mir nicht sicher, was du meinst. Nehmen Sie eine Diophantingleichung mit der Eigenschaft, dass " E keine Lösungen hat", die in ZFC nicht zu entscheiden ist. Mein Punkt ist, dass jeder, den ich kenne, glaubt, dass entweder E Lösungen hat oder nicht, und dass wir es einfach nicht so oder so beweisen können. Glauben Sie, dass es keine Tatsachen darüber gibt, ob E Lösungen hat - dass E weder Lösungen hat noch keine hat? EEEEE
Timothy Chow
4
@vzn: Ich denke, Sie verpassen den Punkt völlig. Die Frage ist nicht, ob eine bestimmte Aussage unentscheidbar ist , sondern ob sie weder wahr noch falsch ist . Die beiden Konzepte sind völlig unterschiedlich. Würden Sie zum Beispiel sagen, dass ZFC weder konsistent noch inkonsistent ist? Alle (anderen), die ich kenne, glauben, dass entweder ZFC konsistent ist oder nicht, obwohl wir möglicherweise keine Möglichkeit haben, festzustellen, was der Fall ist.
Timothy Chow
3
"Das klingt für mich nach Religion und nicht nach Mathematik" - Willkommen in der Metamathematik. Vielleicht ist es eine weniger zu beanstandende Art zu sagen, dass "X weder wahr noch falsch ist", dass wir keinen a priori Grund haben, ein axiomatisches System vorzuziehen, in dem X wahr ist, gegenüber einem axiomatischen System, in dem X falsch ist. Wir haben ein (fast) allgemein anerkanntes Standardmodell der Arithmetik; Als soziale Konvention akzeptieren wir arithmetische Aussagen, die in diesem Modell als wirklich, tatsächlich wahr gelten. Das Gleiche gilt nicht für die Mengenlehre.
Jeffs
2
Siehe auch consc.net/notes/continuum.html und mathoverflow.net/questions/14338/… - Die persönliche Mischung aus Formalismus, Platonismus und Intuitionismus jedes Mathematikers ist im Wesentlichen eine religiöse Überzeugung.
Jeffs
2
@vzn: Sie verpassen immer noch den Punkt. Selbst wenn wir Ihnen Ihre persönlichen religiösen Überzeugungen einräumen, ist alles, was Sie sagen, dass Sie sich Aaronson und dem Rest der Welt nicht anschließen würden, wenn Sie arithmetische Sätze für wahr oder falsch erklären. Wir sind uns alle einig, dass es keine Möglichkeit gibt, anhand der Form einer Aussage zu sagen, ob sie unentscheidbar ist , aber das ist nicht die Behauptung. Der Anspruch ist , dass fast alle außer Sie hat starke Intuitionen haben , dass arithmetische Aussagen sind entweder wahr oder falsch . Nur weil Sie diese Überzeugung nicht teilen, heißt das nicht, dass andere sie nicht haben.
Timothy Chow
11

Dies ist eine berechtigte Frage, auch wenn sie vielleicht etwas unglücklich formuliert ist. Die beste Antwort, die ich geben kann, ist diese Referenz:

Scott Aaronson: Ist P gegen NP formal unabhängig . Bulletin der Europäischen Vereinigung für Theoretische Informatik, 2003, vol. 81, Seiten 109-136.

Abstract: Dies ist eine Umfrage über die Titelfrage, die für Personen geschrieben wurde, die (wie der Autor) Logik als verbietend, esoterisch und fern von ihren üblichen Anliegen betrachten. Ausgehend von einem Crashkurs über die Mengenlehre von Zermelo Fraenkel wird die Unabhängigkeit von Orakeln erörtert. natürliche Beweise; Unabhängigkeitsergebnisse von Razborov, Raz, DeMillo-Lipton, Sazanov und anderen; und Hindernisse, um P vs. NP unabhängig von starken logischen Theorien zu beweisen. Es endet mit einigen philosophischen Überlegungen, wann man erwarten sollte, dass eine mathematische Frage eine definitive Antwort hat.

Andrej Bauer
quelle
2
Ich habe die Tatsache, dass Aaronsons Artikel bereits in den Kommentaren erwähnt wurde, total vermisst. Entschuldigen Sie.
Andrej Bauer
7

[ZFC][1]. Es bedeutet einfach, dass die Theorie weder die Aussage noch ihre Negation beweisen kann. Es bedeutet nicht, dass die Aussage keinen Wahrheitswert hat, es bedeutet nicht, dass wir den Wahrheitswert der Aussage nicht kennen können, wir könnten neue vernünftige Axiome hinzufügen, die die Theorie stark genug machen, um in der Lage zu sein die Aussagen oder ihre Verneinung zu beweisen. Am Ende ist Beweisbarkeit in einer Theorie ein formaler abstrakter Begriff. Es bezieht sich auf unsere reale Erfahrung nur als Modell.

P

Σ1Π1Topologie über Logik ", 1996.)

PNPΣ2, und durchsuchen Sie die Beiträge in der FOM-Mailingliste .

Kaveh
quelle
4

Wie in diesem Papier bewiesen:

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf

Wenn gezeigt werden kann, dass P! = NP unabhängig von der Peano-Arithmetik ist, hat NP extrem nahe an der polynomdeterministischen Zeitobergrenze. In einem solchen Fall gibt es insbesondere einen DTIME (n ^ 1og * (n)) - Algorithmus, der SAT in unendlich vielen großen Intervallen von Eingabelängen korrekt berechnet.

Eine lebenswichtige
quelle
0

Nur ein paar Gedanken darüber. Zögern Sie nicht zu kritisieren.

Sei Q = [kann nicht beweisen (P = NP) und kann nicht beweisen (P / = NP)]. Angenommen, Q ist ein Widerspruch. Ich gehe auch davon aus, dass alle bekannten Entdeckungen über P vs NP noch möglich sind. Insbesondere sind alle NP-Probleme in dem Sinne äquivalent, dass Sie, wenn Sie eines davon in Polynomzeit lösen können, alle anderen in Polynomzeit lösen können. Also sei W ein NP-vollständiges Problem; W repräsentiert gleichermaßen alle Probleme in NP. Wegen Q kann man keinen Algorithmus A erhalten, um W in der Polynomzeit zu lösen. Ansonsten haben wir den Beweis, dass P = NP ist, was Q (1) (*) widerspricht. Beachten Sie, dass alle Algorithmen per Definition berechenbar sind. Zu sagen, dass A nicht existieren kann, bedeutet, dass es keine Möglichkeit gibt, W in der Polynomzeit zu berechnen. Dies widerspricht jedoch Q (2). Wir müssen entweder (1) oder (2) ablehnen. Jeder Fall führt zu einem Widerspruch. Also ist Q ein Widerspruch,

(*) Sie könnten sagen: "Aha! A könnte existieren, aber wir können es einfach nicht finden." Nun, wenn A existiert, können wir alle Programme durchlaufen, um A zu finden, indem wir von kleineren Programmen zu größeren Programmen zählen, beginnend mit dem leeren Programm. A muss endlich sein, weil es ein Algorithmus ist. Wenn also A existiert, muss das Aufzählungsprogramm, um es zu finden, enden.

Thomas Eding
quelle
1
@ Victor: Guter Punkt. Ich stelle mir vor, wenn A existiert, kann man einfach jedes aufgezählte Programm analysieren, um zu sehen, ob es tatsächlich ein NP-vollständiges Problem in der Polynomzeit löst. Ich glaube, da man mit einem endlichen Befehlssatz arbeitet (der von einem Universalcomputer gegeben wird), kann A identifiziert werden. Aber ich bin kein Experte.
Thomas Eding
1
Das Problem ist, dass wenn Q wahr ist, wir in einen Fall fallen würden, in dem niemand, egal wie intelligent, beweisen könnte, dass ein bestimmter vom Enumerator generierter Algorithmus X P = NP löst, auch wenn dies der Fall ist. Dh in diesem Fall existiert ein Algorithmus, um festzustellen, ob P = NP vorhanden ist und gefunden werden kann, aber es ist unmöglich, seine Richtigkeit analytisch zu beweisen. Weiterhin eine Aussage wie "Löst der Algorithmus X das P = NP-Problem?" klingt sehr unentscheidbar.
Victor Stafusa
1
Also ... Wenn A existiert, dann sei N die Größe von A. Sei T die Menge aller Programme mit der Größe <= N. Man kann gleichzeitig W auf allen A 'in T ausführen. Wenn jedes A' endet, laufe die Ausgabe O durch ein Programm, das prüft, ob O W löst. (Beachten Sie, dass jede sogenannte "Lösung" für ein NP-vollständiges Problem in Polynomzeit überprüft werden kann.) Wenn O eine korrekte Antwort ist, schalten Sie alle anderen Computer aus und gebe O zurück. Denke daran, dass nicht jedes A 'enden muss, weil A eines von ihnen ist und ein korrektes O in der Polynomzeit ausgibt. Man muss also nicht einmal nachweisen, dass A P = NP löst. N existiert per Definition.
Thomas Eding
1
In Ihrem (*) Abschnitt: "A muss endlich sein, weil es ein Algorithmus ist. Wenn also A existiert, muss das Aufzählungsprogramm, um es zu finden, enden." Dies bedeutet, dass der Enumerator in der Lage sein sollte zu bestimmen, ob das gerade erzeugte Programm ein NP-vollständiges Problem in der Polynomzeit löst, was sicherlich nicht zu entscheiden ist (noch mehr, da wir hier Q annehmen), und der Enumerator daher niemals anhält .
Victor Stafusa
3
"P = NP ist unabhängig von ZFC" ist nicht dasselbe wie "wir können keinen Algorithmus finden, um ein Problem in NP in deterministischer Polynomzeit zu lösen", wie Victor hervorgehoben hat. Die genauen Definitionen dieser Klassen sind ziemlich wichtig, wenn es um Begriffe wie Unabhängigkeit in Bezug auf eine Theorie geht.
András Salamon