Was wären die realen Implikationen eines konstruktiven

Ich verstehe das Problem auf hohem Niveau und verstehe, dass es die Tür für die Lösung zahlreicher Probleme im Bereich der Informatik öffnen würde, wenn es sich mit einer bereitgestellten Lösung als absolut "erwiesen" herausstellen würde.$P=NP$

Meine Frage ist, wenn jemand einen unbestreitbaren, konstruktiven Beweis für , welche unmittelbaren Auswirkungen würden wir auf eine solche Entdeckung haben? $P=NP$

Ich frage nicht nach einer Meinung darüber, wie die Welt in 5-10 Jahren aussehen würde. Ich bin vielmehr der Meinung, dass dies ein so grundlegend unlösbares Problem ist, dass es die Art und Weise, wie wir rechnen, radikal verändern könnte ... viele Dinge (ja, hier zeigt sich meine Unwissenheit ...), die wir heute nicht leicht berechnen können .

Welche unmittelbare Auswirkung hätte ein gründlicher, genauer und konstruktiver Beweis von auf die Praxis?$P=NP$

Die Leute haben gute Antworten gegeben, wenn man annimmt, dass mit einer wirklich großen Konstante ist. Ich werde den Optimisten spielen und davon ausgehen, dass wir einen Beweis für P = N P mit einer sehr kleinen Konstante finden. Vielleicht nicht wahrscheinlich, aber ich werde versuchen, einen Einblick zu geben, was passieren würde, wenn wir alle N P- Probleme effizient lösen könnten .$P=NP$$P=NP$$NP$

• Compiler: Einige Computerprogramme würden etwas schneller werden, da Compiler für die Registerzuweisung die Grafikfarbe verwenden. Wir wären in der Lage, eine große Anzahl von Registern genau zuzuordnen. Bestehende Compiler, die eine ungefähre Lösung (wie Akkorddiagramme) verwenden, würden eine bessere Ausgabe erhalten, und diejenigen, die eine genaue Lösung verwenden, würden eine schnellere Ausgabe erhalten.

• Standort der Einrichtung: Unternehmen könnten den optimalen Ort für die Platzierung von Fabriken und Lieferdepots für den Versand an ihre Filialen finden, wenn möglicherweise Tausende von Filialen und Fabriken vorhanden sind. Wäre wahrscheinlich keine enorme Verbesserung gegenüber modernen Annäherungen, würde aber die Kosten senken.

• Flugtickets kaufen: Flugtickets sind seltsam, da sie nicht der Dreiecksgleichheit folgen. Manchmal ist es billiger, von A -> B -> C zu fliegen als direkt von A -> C, was beim Modellieren von Entfernungen nicht auffällt. Es wäre einfach, eine Website zu erstellen, die die absolut günstigste Abfolge von Flügen findet, die eine Reihe von Städten besuchen und in Ihrer Heimatstadt beginnen und enden.

• Schaltungsdesign: Elektrische Schaltungen auf einem Chip sind im Grunde boolesche Formeln. Dinge wie die Minimierung könnten effizient berechnet werden, damit unsere Hardware ein bisschen effizienter wird.

• $P=NP$

$NP$

$n$$2^{100} n$$n^{100}$

$\neq$

Was passiert hier? Es gibt verschiedene Probleme mit der Frage P vs. NP:

1. Es geht nur um den schlimmsten Fall.
2. Es ist nur asymptotisch.
3. Alle Polynomzeitgrenzen sind gleich.

Diese Probleme werfen Zweifel an der Relevanz für die reale Welt auf. Jetzt könnte es passieren, dass für 3SAT ein sehr schneller Algorithmus gefunden wird, der sogar symmetrische Verschlüsselungen aufhebt. Ich halte dies jedoch für sehr unwahrscheinlich. Andererseits ist es vollkommen konsistent, dass P sich von NP unterscheidet, während berücksichtigt wird, dass es praktisch ist; Dies würde bestimmte Verschlüsselungsverfahren mit öffentlichen Schlüsseln unterbrechen. Dies ist eine wahrscheinliche Situation, die Auswirkungen hätte, aber nichts mit der Frage von P gegen NP zu tun hat.

Die P vs. NP-Frage mag aus mathematischer Sicht natürlich sein, aber ihre praktische Relevanz ist aus meiner Sicht zweifelhaft. Andererseits könnte die Forschung zu dieser Frage praktische Auswirkungen haben oder auch nicht. es wird nicht von diesem Aspekt geleitet.

$\sf P = NP$$\sf NP \subseteq BPP$

$\sf NP$

[1] Russell Impagliazzo. Eine persönliche Sicht auf die Komplexität von Durchschnittsfällen. Komplexitätskonferenz, 1995.

Auch ohne P = NP sind die heutigen Computer unglaublich leistungsfähig.

• 12873891274647018937561708356916501047777612653914909670721635802187 kann von einem einzelnen Computer in weniger als einer Sekunde verarbeitet werden.
• Für schwierigere Aufgaben wie das Synthetisieren des elektrischen Layouts eines Chips aus einer Beschreibung seiner Funktionen auf höherer Ebene oder das Korrigieren von Fotomasken, um Artefakte aus dem Herstellungsprozess zu kompensieren, arbeiten mehrere hundert Computer einen ganzen Tag, um das Unmögliche zu ermöglichen.
• Heutige Computer sind in der Lage, mathematische Theoreme zu beweisen, die kein Mensch beweisen konnte, wie beispielsweise, dass Robins-Algebren Boolesch sind oder dass eine bestimmte Konstante, von der angenommen wird, dass sie nicht begrenzt ist ( Erdős Diskrepanzproblem ), größer als 2 ist.
• Statische Quellcode-Analyseprogramme können Schwachstellen wie den Heartbleed-Bug identifizieren .
• Automatisierte Argumentationswerkzeuge wie prover9 oder the-E-theorem-prover können die meisten der gebräuchlichen algebraischen Charakterisierungen von inversen Halbgruppen und stark regulären Ringen ohne ausdrückliche Hilfe nachweisen.

Edit 22 Jan 2018 Ich habe jetzt herausgefunden, wie ich den im folgenden Beispiel zitierten Text "interpretieren" sollte. Es war meine eigene Schuld, das inverse Element musste eindeutig sein . Hier ist meine Eingabedatei vom 22. Dezember 2014 ( addinvrig.in ) und hier ist die feste Eingabedatei vom heutigen Tag ( addinvrigFixed.in ). Das Entscheidende ist: (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).Die Leistungsfähigkeit der automatischen Argumentationswerkzeuge selbst fasziniert mich immer noch, auch wenn sie mich nicht davor bewahren können, die Schriften anderer Menschen falsch zu interpretieren.

Die Verwendung automatisierter Argumentationstools ist für mich überraschend nützlich, wenn ich auf zitierte Theoreme stoße, bei denen ich nicht sicher bin, wie ich den Text "interpretieren" soll :

$x, y \in S$$(x \cdot y)' = x' \cdot y = x \cdot y'$$x' \cdot y' = x \cdot y$
$a \in aS \cap Sa$$a \in S$$S$

Ich habe meine prover9-Eingabedateien für diesen Satz angepasst und wurde sofort als Gegenbeispiel für den Satz gezeigt. Ein geringfügiges Modifizieren der Annahmen führte zu vielen ähnlichen wahren Theoremen, was es höchstwahrscheinlich macht, dass Karvellas tatsächlich einen korrekten Theorem aufstellte und bewies, der hier nur falsch zitiert wurde. Googeln nach dem Hinweis auf diesen Satz brachte nur eine weitere Veröffentlichung hervor, in der Karvellas noch ungenauer zitiert wurde .

Dies ist eine unglaublich unvollständige Sammlung computerunterstützter Ergebnisse für spezifische Probleme, die im Allgemeinen nicht zu lösen sind, wenn P! = NP. Vielleicht macht diese Sammlung zumindest einigen Lesern klar, dass wir alle dazu neigen, die Leistungsfähigkeit von Computern in diesem Bereich zu unterschätzen. Viele andere Antworten auf diese Frage scheinen darauf hinzudeuten, dass es keine großen Konsequenzen geben würde, wenn Computer (geringfügig) besser in der Lage wären, hartnäckige Probleme zu lösen. Aber Computer sind immer besser in der Lage, unlösbare Probleme zu lösen (da viel Zeit und Geld aufgewendet wird, um dies zu erreichen), und dies hat sehr reale Konsequenzen. Wenn P = NP bewiesen würde, würde vielleicht das Bewusstsein dafür, was Computer tatsächlich können (auch heute noch), steigen und mehr Menschen würden Computer verwenden, um ihnen bei solchen Aufgaben zu helfen. (PS: Ich bin überzeugt, dass P! = NP,

Es gibt viele Meinungen zu den realen Auswirkungen von P = NP. Wie aus anderen guten Antworten hervorgeht, gibt es hauptsächlich zwei Denkschulen. Einer ist, dass ein P-Zeit-Algorithmus aufgrund von "unerwarteten Anomalien", die mit der Abstraktion verbunden sind, möglicherweise sehr schwierig oder nicht realisierbar ist. z.B:

• Das Programm ist möglicherweise zu "groß", um tatsächlich Code zu schreiben
• Es könnte sich um eine sehr große Konstante handeln, sodass sie für alle Instanzen, die sich in Reichweite der "terrestrischen Berechnung" befinden, noch lange andauert, dh die Effizienz greift nur bei sehr großen Instanzen. Es ist bekannt, dass einige Algorithmen tatsächlich in diesen Fall passen, wie kürzlich von Knuth ausgeführt (Frage 15).

Im Allgemeinen bin ich auf der Suche nach mehr Fokus auf Algorithmen, die in Bezug auf Probleme, deren Größe n machbar ist, schnell funktionieren. Der größte Teil der heutigen Literatur befasst sich mit asymptotisch großen Algorithmen, die jedoch nur dann hilfreich sind, wenn n die Größe des Universums überschreitet.

Eine berühmte Fallstudie stammt von Impagliazzo, wie in einer anderen Antwort von J. zitiert. Sein Aufsatz wurde jedoch in der Zwischenzeit etwas extrapoliert. Hier ist eine großartige neue Referenz von einem Experten, der sich in einer Art Science-Fiction-Zukunftsszenario mit dieser Frage befasst, ch2 / p11. zusammenfassend

Das goldene Ticket: P, NP und die Suche nach dem Unmöglichen von Lance Fortnow

• "Wenn sich herausstellt, dass P = NP und wir effiziente Algorithmen für alle NP - Probleme haben, wird sich die Welt auf eine Weise verändern, die das Internet wie eine Fußnote in der Geschichte erscheinen lässt. Es wäre nicht nur unmöglich, alle diese Änderungen zu beschreiben, sondern auch die Die größten Auswirkungen der neuen Technologien wären unmöglich vorherzusagen. "

• Algorithmus schnell auf Supercomputer implementiert. Boeing beauftragt umgehend mit der Entwicklung eines besseren Tragflächendesigns für ein neues Flugzeug, mit dem es nonstop von London nach Sydney fliegen kann.

• Suchalgorithmus, der verwendet wird, um einen neuen Algorithmus zu finden, der noch schneller ist und die ursprüngliche P = NP-Lösung optimiert. Endet mit dem Ergebnis von 42 Millionen Zeilen unverständlichem Code. Nannte den "Urbana-Algorithmus"

• Algorithmus, der verwendet wird, um maßgeschneiderte Krebsbehandlungen / Nahkuren zu finden, die auf Einzelpersonen zugeschnitten sind. heilt Krebs, AIDS, Diabetes, aber die Erkältung bleibt ein Rätsel

• Mit dem Super-Scheduling-Algorithmus können Prognostiker "unglaubliche Fortschritte bei der Wettervorhersage erzielen und Temperatur, Wind, Wolkendecke und Niederschlag fast ein Jahr im Voraus genau vorhersagen. Ähnliche Algorithmen retten jetzt Leben, indem sie Stürme, Tornados und Hurrikane genau vorhersagen, damit die Menschen dies können nach Bedarf vorbereiten oder evakuieren. "

• Hochgenaue Gesichtserkennung

• Der Computer kann 3D-Modelle einer Szene in Echtzeit aus verschiedenen Kamerawinkeln rekonstruieren

• Computeralgorithmen steuern den Kamerabetrieb für Sportereignisse (anstatt von Menschen gesteuert)

• Automatisierte Kommentare und Wiederholungen werden vom Algorithmus generiert, einschließlich ausgewählter Blickwinkel und Statistiken, und in Echtzeit in jeder Sprache erstellt

• Fantasy-Baseball / Sport nehmen mit hochpräzisen Simulationen eine neue Dimension an

• Der Geschmack der Speisen wird durch den Algorithmus verbessert

• Der Algorithmus könnte verwendet werden, um "so ziemlich alles zu lernen, einschließlich was gute Kunst, populäre Musik und Wörter ausmacht, die die Seele bewegen. Denken Sie daran, dass P = NP bedeutet, was wir testen können, was wir finden können. Wenn Sie also einen Algorithmus haben." Um Größe zu erkennen, können Sie den Algorithmus erneut verwenden, um diese Größe schnell zu finden. "

• Der Politiker verwendet einen Computeralgorithmus, um großartige Reden zu erkennen und eine zu generieren, die den Mustern entspricht. Die Sprache im Internet wird viral.

• Menschen erzeugen komplette Kunstwerke aus unvollständigen / unvollendeten Kunstwerken, zB Symphonien. Sie verwenden Algorithmen, um neue Beatles / Elvis-Datensätze zu generieren. Neue Kunst, Romane, Theaterstücke und Gedichte, zB romantische Komödie mit Humphrey Bogart / Julia Roberts.

• Amazon kann auf Anfrage maßgeschneiderte Romane für Einzelpersonen erstellen. NBC erstellt Live-Action-Adventure-Fernsehserien, die vollständig vom Computer erstellt wurden

• Simulierte virtuelle Realität in Videospielen, die beliebige Aktionen der Spieler anstelle eines festgelegten Satzes möglicher Handlungsstränge zulässt.

• Strafverfolgungsbehörden verwenden Algorithmen als "unglaubliches Instrument zur Aufklärung von Verbrechen, das anscheinend das Unmögliche tut, um Verdächtige aufzuspüren". Computeralgorithmus kann wahrscheinliche Gesichter (für zusammengesetzte Skizzen) nur mit DNA rekonstruieren. Die Polizei ermittelt einen Mordverdächtigen anhand einer umfangreichen Suche in der Datenbank mit Führerscheinfotos, die an der generierten Skizze (aus DNA) ausgerichtet ist.

Leider wird nicht viel, was Fortnow oben skizziert, von aktueller wissenschaftlicher Literatur gestützt, außer vielleicht einer einfallsreichen Extrapolation von Impagliazzos-Welten. es würde viel mehr erfordern, um diesen Punkt für Punkt zu analysieren, aber zusammenfassend scheint alles unterhaltsames, aber fantastisches / Wunschdenken zu sein (oder vielleicht ist das sein verschleierter Punkt). Tatsächlich gibt es wissenschaftliche Prinzipien, die mit vielen der Punkte in Konflikt stehen. Und beachten Sie, dass Fortnow ein Sportfan ist und in diesem Bereich eine erweiterte Metapher entwickelt. Könnte dies eher ein Hinweis darauf sein, dass Menschen in Rillen denken ?

Zum Beispiel ist bekannt, dass der "Schmetterlingseffekt" darauf hindeutet, dass eine genaue Wettervorhersage über einen (etwa) Mehrtageshorizont hinaus aufgrund der "empfindlichen Abhängigkeit von den Anfangsbedingungen" unmöglich ist (und Fortnow hat später in seinem Blog zugestanden, genau dies wiederholt zu kritisieren Punkt). Es gibt auch viele Beweise dafür, dass Computer bei hochmenschlich-subjektiven Aufgaben, wie dem Erzeugen oder Identifizieren einflussreicher Kunst, versagen (eine Aufgabe, die selbst erfahrene Menschen nicht konsequent lösen können).

Tatsächlich geht die ganze Frage von einer kontrafaktischen oder falschen Voraussetzung aus . Beachten Sie, dass eine große Mehrheit der befragten Experten denkt / glaubt, trotz des Mangels an bislang unbestreitbaren Beweisen, P ≠ NP. und es ist natürlich, es mit anderen bekannten Gesetzen / Beschränkungen / Beschränkungen wie der Thermodynamik (z. B. Unmöglichkeit der ständigen Bewegung / freien Energie ) und Statistiken zu vergleichen, z. B. dem Satz "kein freies Mittagessen" .

Das Fazit ist also, dass vielleicht sogar erfahrene Wissenschaftler das Ergebnis von P = NP nicht genau vorhersagen können. Die vielleicht beste Antwort für den Moment ist zuzugeben, dass die Menschen derzeit keine gute Antwort haben.

P gegen NP, technisch gegen moralisch

$O(n^2)$$O(n^{\lg^* n})$$2^{65536}+2^{1024}n^{256}$$O(n^{\lg n})$

Was passiert also, wenn P = NP moralisch wahr ist?

$Q$$Q$Richtig, dann können all diese Probleme sehr schnell gelöst werden. Um nur ein Beispiel zu nennen, Sie können die besten Gewichte für sehr komplizierte Modelle des maschinellen Lernens lernen. Sie können Verschlüsselungsprotokolle unterbrechen.

$\neq$

$\neq$

$\neq$

$\neq$

$\neq$

Wenn Sie wissen, dass Sie ein NP-vollständiges Problem nicht bei allgemeinen Eingaben, sondern bei Eingaben mit bestimmten Eigenschaften lösen möchten, müssen Sie sich nicht um das allgemeine Problem kümmern. Sie müssen nur das einfachere Problem lösen. Leider ist es oft nicht einfach festzustellen, welche Art von Eingaben Sie in der Praxis interessieren.

$\neq$

Welche nahezu unmittelbare Auswirkung hätte ein gründlicher, genauer Nachweis von P = NP mit einer bereitgestellten Lösung auf die Praxis?

Es würde wahrscheinlich eine Menge großartiger Dinge daraus werden, aber das würde niemanden interessieren.

Das Problem ist , dass die Grundlage für (fast) all moderne Verschlüsselung auf der Annahme , dass P basiert nicht gleich NP. Die Verschlüsselung, die Ihr Kennwort schützt, während es über das Internet übertragen und in Datenbanken gespeichert wird. Die Verschlüsselung, die Kreditkartendaten schützt , während diese über das Internet übertragen werden ... Die Verschlüsselung, die Milliarden von täglichen Finanztransaktionen schützt, die unsere globale Wirtschaft in den riesigen Organismus einbinden, der sie ist.

Im besten Fall bedeutet P = NP, dass aufhört. Die Leute verwenden wieder Bargeld, und Banken versuchen, diese Bargeldabhebungen auf einem nicht verbundenen Medium aufzuzeichnen, da Transaktionen an eine Zentrale nicht mehr vertrauenswürdig sind. Dies dauert möglicherweise einige Monate, bis eine bessere Verschlüsselung weltweit implementiert ist. I'm besten fall.

Im schlimmsten Fall bedeutet P = NP, dass jemand die Welt zerstört. Die Währung baut auf dem Konzept des Vertrauens auf. Sie schätzen einen Dollar, weil Sie darauf vertrauen, dass Ihr Nachbar Ihnen Waren oder Dienstleistungen im Wert von einem Dollar dafür gibt. Sie schätzen Ihren Computer und sagen, dass Sie 500 Dollar auf der Bank haben, weil Sie Ihre Karte klauen und Waren und Dienstleistungen im Wert von 500 Dollar erhalten können ...

Was wäre, wenn du dem nicht trauen könntest ? Wenn P = NP, könnte sich jemand als verschiedene Banken, Regierungen und Personen ausgeben und den Währungsbetrag auf jedem Konto effektiv zufällig bestimmen. Löschen Sie die Währung in jedem Konto. Sicher, verschiedene Banken haben Backups, aber wie lange ist ihre Verschlüsselung aufgebrochen? Welche Transaktionen waren gut und welche waren falsch? Es ist unmöglich zu wissen.

Sobald dieses Vertrauen gebrochen ist, entsteht Chaos. Alle Vorteile, die sich beispielsweise aus der Bewältigung des Problems des Handlungsreisenden ergeben, werden ignoriert, da die Menschen Schwierigkeiten haben, sich selbst zu ernähren.

Die Realität liegt wahrscheinlich irgendwo dazwischen, aber hoffentlich zeichnet dies ein ausreichend großes Bild davon, wie wichtig dieses Problem ist.

Der Aufwand für Geräte, Strom und Cloud-Ansätze wird massiv sinken. Viele Dinge werden gerade mit brachialer Gewalt berechnet, oder Näherungen, die immer noch einiges an brutaler Gewalt erfordern. Wir werden nicht mehr alle diese massiv paralisierten Brute-Force-Berechnungen durchführen.

Dies ist keineswegs die einzige Verwendung von Cloud-Computing, wird sich aber dennoch spürbar auf den Energieverbrauch, die Cloud-Verarbeitung usw. auswirken. Allein die Energieeinsparungen könnten sich auf unseren CO2-Fußabdruck auswirken.

Die KI wird auch viel besser. Wir könnten endlich einen Computer haben, der die besten GO-Spieler sein kann, und Ihr Grafikrechner wird Sie beim Schach schlagen.

$\ne$

Und die Vermutung, die widerlegt wird, bedeutet nicht, dass alle Probleme von praktischem Nutzen mit einem Fingerschnipp gelöst würden. Erstens können sie immer noch härter sein als NP.