Nachweis von P = NP ohne mathematische Aussagen / Computerprogramm

13

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.

Raphael
quelle
10
Siehe diese Sammlung: win.tue.nl/~gwoegi/P-versus-NP.htm . Du willst nicht einer von ihnen werden.
Yuval Filmus
es gibt einen möglichen "schwachen" Präzedenzfall dafür. Godels thm und Diagonalisierung können lose auf Richards Paradoxon gegründet worden sein, das von der literarischen Arbeit war. Beachten Sie jedoch, dass es äußerst fortgeschrittener Mathematiker bedurfte, um es in legitime mathematische Aussagen / Eigenschaften umzuwandeln.
vzn
@vzn: die Wikipedia-Seite, die Sie mit Richard's Paradox bis 1905 verknüpfen; Die Diagonalisierung stammt aus dem Jahr 1891. Richards Paradoxon basiert also wahrscheinlich auf der Diagonalisierung, nicht umgekehrt.
Niel de Beaudrap
@NieldeBeaudrap, vzn: Ihre Kommentare wurden zu einer Unterhaltung, und ich habe sie zum Chatten verschoben. Fahren Sie dort fort.
Gilles 'SO- hör auf böse zu sein'

Antworten:

16

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

phant0m
quelle
14
Lassen Sie uns hier niemanden falsche Hoffnungen machen. Es ist äußerst unwahrscheinlich, dass ein Laie gegen N P lösen kann oder dass die Lösung in "normalem Englisch" ausgedrückt werden kann. Es gibt bessere Dinge für Laien, als zu versuchen, die schwierigsten mathematischen Probleme zu lösen. PNP
Andrej Bauer
3
@AndrejBauer Klar, ich wollte nicht implizieren, dass es wahrscheinlich ist. Ich gehe davon aus, dass Sie eine Antwort ähnlich der von Niel besser gefunden hätten. Aber während es die Dinge gut relativiert, spricht es die gestellte Frage nicht wirklich an.
Phant0m
3
Ich weiß, dass Sie so etwas nicht implizieren wollten. Ich wollte nur eine ausdrückliche Warnung ausdrücken, damit ein Journalist oder jemand dies liest und meint, vs. N P werde von einem Literaturkritiker gelöst. PNP
Andrej Bauer
@ phant0m: Ich bin neugierig. Befasst sich mein erster Absatz nicht mit der eigentlichen Frage?
Niel de Beaudrap
@NieldeBeaudrap Sicher, es spricht es an, aber es scheint, als ob die Schlussfolgerung gefolgert werden muss. Nebenbemerkung: Man könnte den "Indeed"Satz auch so interpretieren, als würde er einen Beweis in Worten erklären, aber es wäre an sich kein Beweis. Auch eine Turingmaschine an sich ist kein Beweis, es sei denn, es liegt ein Beweis für die Richtigkeit vor. Dies impliziert auch, dass die Darstellung eines TM über ein Flussdiagramm als "Beweis" von Natur aus überlegen ist, auch wenn dies nicht der Fall ist.
Phant0m
19

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

Niel de Beaudrap
quelle
2
Obwohl alles, was Sie sagen, wahr ist, befürchte ich, dass diese Denkweise (die sich auf dem Gebiet durchgesetzt hat, vielleicht als Schutzmechanismus) das autodidaktische Genie entmutigen könnte, das das Problem heute lösen könnte. Ich denke, eine hilfreiche Botschaft ist: Gehen Sie und lernen Sie so viel, wie Sie brauchen, um auch nur einen Fachmann davon zu überzeugen, zuerst Ihre Arbeit zu lesen und dann ihre Gültigkeit zu prüfen. Es könnte Jahre dauern, aber das ist der richtige Weg.
Raphael
6
@Raphael: Ich denke, dass meine Mentalität sogar perfekt auf die Möglichkeit eines Autodidakten abgestimmt ist. Meine Botschaft an das autodidaktische Genie lautet: Einerseits bedeutet nicht akademisch zu sein, dass Sie kein Mathematiker sind - und dass ich eine Antwort nach ihrer Qualität beurteilen würde. So ist die Beweislast auf diesem Autodidakten Genie , um sicherzustellen , dass die Antwort hat die Qualität und vorsichtig von den Gefahren zu sein , dass Amateure oft zum Opfer fallen.
Niel de Beaudrap
2
Ich befürchte, dass diese Denkweise ... das autodidaktische Genie entmutigen könnte, das das Problem heute lösen könnte. - Gut. Ihr autodidaktisches Genie sollte daran erinnert werden, dass die Messlatte extrem hoch ist und dass Dutzende (Hunderte?) Anderer autodidaktischer Genies versucht haben und es nicht geschafft haben, sie zu erreichen.
JeffE
"Fermats letzter Satz oder die Poincaré - Vermutung. Vielleicht haben sie eines Tages einfachere Beweise, aber die ursprünglichen Beweise bringen Sie weit in die Wildnis, um Sie ans Ende zu bringen (oder im Fall des Vierfarbensatzes ist die Route sehr lang und lang repetitive) ". Dies ist eine faire / vernünftige Erwartung von einigen, aber im Gegensatz zu willkürlichen theoretischen Kuriositäten wie FLT und 4CT kann ein P-gegen-NP-Beweis (grundlegende) Werkzeuge für andere Komplexitätsklassentrennungen und die Komplexitätstheorie im Allgemeinen liefern , oder es könnte sogar ein Rosettastein oder ein fehlendes Glied für eine spätere Weiterentwicklung sein.
vzn
@vzn: Ich bin mir nicht sicher, was Sie mit dieser Unterscheidung erreichen. Nur weil P gegen NP wichtig ist, ist es nicht wahrscheinlicher, dass es eine einfache Lösung gibt, die von einem klugen, aber nicht eingeweihten Amateur gefunden werden könnte.
Niel de Beaudrap
-5

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

Thomas Klimpel
quelle
2
7
Niemand "weiß", dass P! = NP ist. Experten mögen es stark glauben, aber kein Experte weiß es (es sei denn, jemand hat einen Beweis und hat ihn für sich selbst aufbewahrt). Es ist zwar unwahrscheinlich, dass P = NP wahr ist. Als Randbemerkung sollte jeder (insbesondere Wissenschaftler) für alles offen sein, sofern nichts anderes bewiesen ist. In diesem Fall sollte jeder Wissenschaftler, so groß seine Überzeugung ist, dass P! = NP ist, akzeptieren, dass die Möglichkeit besteht, dass P = NP ist.
George
7
In der Mathematik besteht das Problem darin, Beweise zu ignorieren und blindlings voranzuschreiten, dass Sie möglicherweise etwas annehmen, das falsch ist. Dadurch wird die Quest viel langsamer. Die physikalischen Wissenschaften haben dieses Problem nicht (mit Ausnahme von Fällen wie Quantengravitation / Stringtheorie), weil sie mit dem Experiment übereinstimmen müssen.
Peter Shor
1
@ThomasKlimpel: Ich erinnere mich, dass ich diesen Kommentar gepostet habe, aber nicht wo. Angesichts der Tatsache, dass jeder, auf den ich antwortete (Sie?), Ihn lediglich als Autorität benutzte, um für die Richtigkeit des mathematischen Platonismus zu argumentieren, während ich nach einiger Überlegung zu einer formalistischen Position gekommen bin, die bloße Tatsache, dass Godel ohne weiteres eine andere Meinung hatte Ausarbeitung ist in der Tat irrelevant. Technische Argumente werden nicht gewonnen wie Tennisspiele, mit einer schnellen Widerlegung. In ähnlicher Weise werden überzeugende Antworten nicht nur nach ihrer Präzision (obwohl dies hilfreich ist) oder nach ihrer Autorität beurteilt, sondern auch nach ihrem technischen Wert.
Niel de Beaudrap
3