Nachweis von P = NP ohne mathematische Aussagen / Computerprogramm

Dies ist mein erster Beitrag, nachdem ich seit einiger Zeit ein passiver Benutzer bin. Ich möchte einige Fragen stellen, wenn ich darf. Ich bin kein Mathematiker, aber meine Frage bezieht sich auf das Gebiet der Mathematik / Informatik. Insbesondere das P vs NP-Problem. Mir ist bewusst, dass dies ein Problem ist, das Elite-Profis noch nicht lösen konnten ...

Unabhängig davon möchte ich fragen:

Wenn eine Person, die weder Mathematiker noch Programmierer ist, ein Flussdiagramm oder eine Reihe von Schritten in grundlegender englischer Sprache erstellen würde, die angeblich eine Lösung für eines der P-gegen-NP-Probleme bieten, würde dies als „Beweis“ dafür gewertet P = NP .. um den Preis des Clays Institute zu erhalten :)? Oder ist es ein Muss, die Lösung als mathematische Beweise / Computerprogramm zu schreiben?

Vielen Dank.

"Nein", Sie können "Basic English" verwenden.

Wenn Sie erfolgreich waren, hätten Sie einen konstruktiven Beweis erstellt . Beweise in der Mathematik sind oft eine Mischung aus "grundlegendem Englisch", wie Sie es nennen, und mathematischen Formeln, aber sie müssen auch keinen gültigen Beweis enthalten.

Angenommen, Sie haben ein solches Flussdiagramm. Sie müssen also nachweisen - dh argumentieren -, dass Ihr Algorithmus für jede Probleminstanz funktioniert . Die Art und Weise, wie Sie dies tun, liegt ganz bei Ihnen, solange der Beweis eindeutig ist und alle von Ihnen behaupteten Prämissen als wahr erwiesen wurden.

Danach haben Sie einen mathematischen Beweis in der Hand. Eigentlich hätte ich am Anfang " Ja " sagen sollen , Sie brauchen einen mathematischen Beweis .

Eine Turing Maschine, muss daran erinnert werden, ist eine Art Flussdiagramm. So ist die Struktur eines Computerprogramms im Allgemeinen. "Ein Flussdiagramm" in eine formale Antwort auf das Problem zu verwandeln, sollte also ziemlich einfach sein, wenn es tatsächlich funktioniert hat. Wenn man mit einer schrecklich formalen Antwort auf P versus NP anfängt , würden die meisten Informatiker versuchen, eine Formulierung zu finden, die einer einfachen englischen Beschreibung so nahe wie möglich kommt, um ein möglichst tiefes Verständnis der Lösung zu erlangen möglich.

Aber es gibt ein grundlegendes Problem mit der Art von Frage, die Sie stellen. Was bedeutet es für jemanden, der in der Lage wäre, P gegen NP zu lösen - und zu zeigen, dass er gleich ist -, weder Informatiker noch Mathematiker zu sein? Vielleicht sind sie nicht professionell als Informatiker oder Mathematiker angestellt, aber dies ist unerheblich, wenn sie die Fähigkeit haben, das zu lösen, was einige (zum Beispiel Scott Aaronson) als das wichtigste mathematische Problem bezeichnen, das wir jemals in Betracht gezogen haben. Wenn jemand die Ausbildung hat (oder sogar Autodidakt ist), um das Problem erfolgreich anzugehen und die Lösung auch klar an andere weiterzugebenIndem Sie die wichtigsten Unterprogramme und ihre Rolle bei der Lösung von z. B. SAT oder HAMPATH identifizieren, spielt es keine Rolle, ob sie angestellt sind oder sogar einen Abschluss haben. sie sind dann doch Mathematiker oder Informatiker. Noch besser ist es , wenn sie beschreiben , wie ihre Lösungen klassische Hindernisse wie Oracle Ergebnisse, wie Orakel überwinden A , für die P ^A ≠ NP ^A (oder das Gegenteil) , indem zeigen konkret , was die Struktur sortiert in dem Problem der Algorithmus Vorteil nimmt, die wäre im Orakelmodell nicht zugänglich. Das Problem ist jedoch, dass die meisten Menschen davon träumen, P gegen NP als Amateure oder Außenseiter zu lösenOffenbar fehlt es ihnen an Kommunikationsfähigkeiten, um ihre Arbeit tatsächlich angemessen zu beschreiben, oder sie wissen (weil sie nicht genug gelesen haben) nichts über Ergebnisse, die ihre Vorgehensweise zur Lösung des Problems von Anfang an zum Scheitern verurteilt machen würden.

Wie bei allen heutigen Träumen von Ruhm gibt es ein grundlegendes Problem mit der Phantasie, derjenige zu sein, der P gegen NP löst . Das Problem ist, dass es fast unmöglich sein wird. Nicht wirklich unmöglich, wohlgemerkt, oder zumindest nicht unbedingt unmöglich; nur fast so. Als ehrgeiziger Mensch kann man die Tatsache aus den Augen verlieren, dass es viele andere kluge Leute gibt: Viele von ihnen haben auch über das Problem nachgedacht; und viele von ihnen sind sogar um ein paar Größenordnungen heller als wir. Und dass es so kluge Leute gibt, solange das Problem besteht; und doch bleibt es ungelöst. Ja, es ist grundsätzlich möglich, dass jeder falsch darüber nachdenkt, und das schon seit Jahrzehnten. Aber ist das so?wirklich besonders wahrscheinlich? Niemand sollte von sich erwarten, dass er derjenige ist, der den einen Vorzeichenfehler erkennt, den alle anderen machen, denn wenn alle anderen diesen Fehler machen, muss es etwas an dem Problem geben, das dazu führt, dass man denselben Fehler macht. Oder - für den wahrscheinlichen Fall, dass der Grund, warum das Problem ungelöst bleibt, nicht vorliegtdass die Leute immer wieder einfache Fehler machen oder noch nicht an den einen einfachen Trick gedacht haben, der das Ganze auflöst - was das Problem grundlegend schwierig macht, ist im Wesentlichen eine objektive Schwierigkeit des Problems, und keine geschickten Tanzschritte werden es einem erlauben, einfach anmutig zu walzen vorbei an allen Hindernissen; Erforderlich ist ein Ansatz, der nicht nur neuartig, sondern auch tiefgreifend ist und subtile Strukturen identifiziert, die niemand zuvor gesehen hat. Die Art von Struktur, die man am ehesten erkennt, wenn man jahrelang ununterbrochen über das Problem nachdenkt.

Wenn Sie realistisch sein möchten, was zur Lösung des P- gegen- NP- Problems erforderlich ist, können Sie es mit ähnlich berühmten Durchbrüchen in den letzten Jahrzehnten vergleichen, z Poincaré-Vermutung. Vielleicht haben sie eines Tages einfachere Beweise, aber die Originalbeweise bringen Sie weit in die Wildnis, um Sie ans Ende zu bringen (oder im Fall des Vierfarbensatzes ist der Weg sehr lang und wiederholt sich). Es gibt keinen besonderen Grund zu der Annahme, dass P gegenüber NP unterschiedlich sein wird. so dass, wenn es am Ende istVon einem Amateur gelöst, sind die Chancen sehr hoch, dass es sich um jemanden mit ähnlichem Hintergrundwissen und Kenntnis der Techniken von jemandem handelt, der eine akademische Ausbildung hat. Jeder realistische Amateur, der davon träumt, P gegen NP zu lösen, tut gut daran.

Ein Beweis, dass P = NP von einer mathematischen Zeitschrift akzeptiert wird, aber von den Eliteprofis niemals akzeptiert wird. Der Grund ist, dass sie wissen, dass P! = NP (zumindest für alle praktischen Zwecke). Sie wissen auch, dass es unglaublich schwierig ist, dies zu beweisen, und sogar ein Beweis, dass P! = NP von den Elite-Profis mit einem gesunden Maß an Skepsis aufgenommen wird.

Die Eliteprofis haben mehr Gründe, als dass viele kluge Köpfe versucht haben, einen Polynomalgorithmus für NP zu konstruieren oder N! = NP zu beweisen. Sie gehen jedoch davon aus, dass dieses Argument für einen Laien am überzeugendsten sein sollte. Sie haben wahrscheinlich Recht, dass der Verweis auf Barrieren in Bezug auf relativierende Beweise, natürliche Beweise oder algebrierende Beweise für einen Nichtfachmann selten überzeugend ist. Wenn zu viele "Amateure" versuchen, P vs NP auf eine bestimmte Weise aufzulösen (zum Beispiel durch logische Auflösung oder durch Reduzieren auf ein lineares Programmierproblem), dann wird jemand den Schmerz durchmachen (dies dauert manchmal Jahre), um dies zu beweisen Dieser spezifische Anstellwinkel ist wahrscheinlich zum Scheitern verurteilt.

Bearbeiten Ich freue mich, dass diese Antwort weiterhin (negatives) Feedback hervorruft. Lassen Sie mich daher den zweiten Teil der Antwort (der nichts mit dem Feedback zu tun hat, aber vom Hauptpunkt ablenken kann) durch das folgende Zitat aus Truth vs Proof ersetzen :

Wir könnten agnostisch bleiben und sagen, dass wir es einfach nicht wissen, aber es kann zu viel Skepsis in der Wissenschaft geben. Zum Beispiel hat Scott Aaronson einmal behauptet, dass P! = NP in anderen Wissenschaften inzwischen zum Naturgesetz erklärt worden wäre. Ich neige dazu, zuzustimmen. Schließlich versuchen wir, die Wahrheit über die Art der Berechnung aufzudecken, und diese Suche wird nicht schneller verlaufen, wenn wir darauf bestehen, alle Beweise zu verwerfen, die nicht in Form von mathematischen Beweisen aus ersten Prinzipien vorliegen.

Diese Änderung soll nicht die Anzahl der Rückmeldungen verringern, sondern ganz klar machen, dass diese Antwort die Tatsache ernst meint, dass die Experten "wissen, dass P! = NP", obwohl sie dies nicht beweisen können.

23. November 2013 Nochmals vielen Dank für das Feedback. Für die Aufzeichnung hat die Antwort jetzt 7 downvotes, 1 upvote und 14 Kommentare (8 von mir). Aufgrund der Menge an Kommentaren sind interessante Verweise und Begründungen in den Kommentaren ausgeblendet. Deshalb habe ich mich entschlossen, einige davon hier hinzuzufügen:

• Wie Gödel selbst an von Neumann schrieb, wenn P = NP "für alle praktischen Zwecke" wahr wäre, dann wäre sein Unvollständigkeitssatz nur theoretisch wahr, aber praktisch falsch.

• In seiner Arbeit von 1971 konnte Stephen Cook ... keine Gegenbeispiele für das Davis-Putnam-Verfahren (gelöst von Haken 1985) erstellen. Heutzutage sind viele Techniken, Ergebnisse und Gegenbeispiele verfügbar, um vorgeschlagene effiziente NP-Löser zu "widerlegen". Auch P = NP widerspricht dem "Gesetz der Erhaltung der Schwierigkeit", der "qualitativen infinitären <-> quantitativen finitären" Entsprechung, ...

• Scott Aaronson hat diesen Kommentar vor langer Zeit geschrieben :

  anonym: Sie behaupten (als Tatsache!), dass 3SAT eine Sprache in NP ist, die nicht in Polynomialzeit berechnet werden kann. Aber du kannst es nicht beweisen. Ist das Ihre wissenschaftliche Methode? Ja. Als überzeugter Anhänger der Wissenschaft und der Vernunft bin ich bestrebt, klar zwischen dem zu unterscheiden, was ich beweisen kann, und dem, von dem ich nur weiß, dass es wahr ist.

• Scott ist dafür bekannt, dass er versucht zu demonstrieren, was es bedeutet, dass er etwas "weiß", indem er beispielsweise 200.000 $ setzt: scottaaronson.com/blog/?p=458