Wie würde sich P = NP auswirken? [geschlossen]

18

Ich bereite mich auf einen Test vor und finde keine eindeutige Antwort auf die Frage: Welche Auswirkungen hätte der Nachweis von PTIME = NPTIME? Ich habe Wikipedia überprüft und es wurde nur erwähnt, dass es "tiefgreifende Auswirkungen auf Mathematik, KI, Algorithmen ..." usw. haben würde.

Kann mir jemand eine Antwort geben?

algorithms complexity latusaki
quelle
Dies hat in keiner Weise mit Softwareentwicklung zu tun. Ich habe vorerst geschlossen, aber die Mods bei Math.StackExchange gefragt, ob sie möchten, dass ich dies für Sie migriere.
maple_shaft

Antworten:

22

Als Erstes fällt ein, dass die Sicherheit der Kryptografie mit öffentlichen Schlüsseln derzeit davon abhängt, dass mathematische Probleme der Schwierigkeitsklasse NP nicht mit Brute-Force-Methoden gelöst werden können. Wenn P = NP, müsste alles, was von PKC abhängt (einschließlich HTTPS, was die gesamte moderne, weltweite E-Commerce-Infrastruktur bedeutet ), überarbeitet werden!

Mason Wheeler
quelle
4
Es würde sicherstellen, dass es Algorithmen gibt, die in polynomialer Zeit ablaufen. Es wäre dann nur ein Countdown, diese Algorithmen zu finden und dann sozusagen Kaboom.
Welt Ingenieur
7
Ein Beweis würde das Finden eines polynomialen Zeitalgorithmus für ein NP-vollständiges Problem beinhalten. Und wenn Sie einen Polynomalgorithmus finden, können Sie damit alle anderen NP-vollständigen Probleme lösen, indem Sie die Probleme auf eine gemeinsame Form reduzieren. Dies bedeutet, dass ein Beweis für P = NP und Algorithmen, die ihn verwenden, gleichzeitig angezeigt wird.
Oleksi
7
Natürlich könnten die konstanten Faktoren so groß sein, dass dies nur ein theoretisches Problem ist ... für einige Zeit.
quant_dev
17
Wenn wir einen solchen Algorithmus finden, hat er möglicherweise immer noch einen schrecklich hohen konstanten Faktor oder einen enormen Grad. Natürlich wäre es ein Warnsignal für alle, sich von den alten Methoden zu entfernen, so wie wir uns von DES entfernt haben, bevor sich herausgestellt hat, dass es lösbar ist, aber die Weltwirtschaft würde nicht sofort zusammenbrechen. Denken Sie nur an Geld selbst: Letztendlich weiß jeder, dass es nicht funktioniert, wenn Sie nicht daran glauben, aber der globale Handel funktioniert immer noch gut.
Kilian Foth
5
Wir würden wahrscheinlich auf einmalige Pads zurückgreifen. Amazon könnte Ihnen einen 1-Gig-Stick zusenden, der mit seiner Website zusammenarbeitet und Sie für den Rest Ihres Lebens in Atem hält.
Macneil
18

Dies wird in Der Status des Problems P versus NP behandelt . Auf jeden Fall eine Lektüre wert.

Ein paar hervorstechende Punkte aus dem Artikel (zitiert aus dem Abschnitt Was ist, wenn P = NP? ):

  • Kryptografie mit öffentlichen Schlüsseln wird unmöglich.
  • Da alle NP-vollständigen Optimierungsprobleme einfach werden, wird alles viel effizienter. Transporte aller Art werden optimal geplant, um Personen und Güter schneller und kostengünstiger zu bewegen. Hersteller können ihre Produktion verbessern, um die Geschwindigkeit zu erhöhen und weniger Abfall zu erzeugen.
  • Das Lernen wird einfach, wenn das Prinzip von Occams Rasiermesser angewendet wird - wir finden einfach das kleinste Programm, das mit den Daten übereinstimmt. Nahezu perfekte Seherkennung, Sprachverständnis und Übersetzung sowie alle anderen Lernaufgaben werden trivial. Wir werden auch viel bessere Vorhersagen über Wetter, Erdbeben und andere Naturereignisse haben.
  • P = NP hätte auch große Auswirkungen auf die Mathematik. Man könnte kurze, vollständig logische Beweise für Theoreme finden, aber diese Beweise sind normalerweise extrem lang. Aber wir können das Occam-Rasiermesser-Prinzip verwenden, um mathematische Beweise zu erkennen und zu verifizieren, wie sie normalerweise in Fachzeitschriften geschrieben werden. Wir können dann Beweise für Theoreme finden, die Beweise mit angemessener Länge enthalten, beispielsweise auf weniger als 100 Seiten. Eine Person, die P = NP nachweist, würde vom Clay Institute nicht mit einem Scheck über 1 Million US-Dollar, sondern mit sieben nach Hause gehen (tatsächlich sechs, da die Poincaré-Vermutung gelöst zu sein scheint).
vinaykola
quelle
2
Ich verstehe nicht, wie P = NP impliziert, dass Kryptographie mit öffentlichen Schlüsseln unmöglich ist. Es legt nahe (impliziert aber nicht), dass aktuelle Implementierungen nicht so schwer zu brechen sind, wie wir es vorher dachten. Aber wie andere darauf hingewiesen haben, hätte P = NP keinen Einfluss auf die Kryptographie mit öffentlichen Schlüsseln, wenn die relevanten Konstanten in einem Algorithmus zur optimalen Zeitreduzierung extrem groß sind.
Emory
+1 für den dritten Aufzählungspunkt - Jeder weiß, dass P = NP die Krypto beeinflussen würde, aber aus irgendeinem Grund hört man selten, wie sich dies buchstäblich auf jede andere Computerdisziplin auf dem Planeten auswirken würde.
BlueRaja - Danny Pflughoeft
@emory: Ich werde nicht so tun, als wäre ich ein Experte, aber ich verstehe, dass wir unseren Ansatz völlig überdenken müssten, wenn ein solcher Algorithmus auch mit einer ziemlich hohen Konstante gefunden würde. Und wer sagt, wenn ein Algorithmus gefunden wurde, können wir keinen anderen mit einer kleineren Konstante finden? Ein Algorithmus würde auch alle anderen NP-vollständigen Probleme lösen. Die unmittelbare Auswirkung mag also nicht groß sein, aber es müsste viel darüber nachgedacht werden, alle vorhandenen Systeme zu ändern.
Vinaykola
Zum ersten Mal hörte ich von dem Prinzip von Occams Rasiermesser. Interessantes ...
UmNyobe
@vinaykola, das P = NP prüft, impliziert nicht, einen Algorithmus zu finden. Natürlich wäre die Suche nach einem Algorithmus der einfachste (aber nicht der einzige) Weg, um P = NP zu beweisen. Wenn die Konstanten dann vernünftig wären, könnten wir uns mit den von Ihnen angesprochenen Fragen befassen.
Emory
7

Die meisten NP-Gesamtprobleme haben "interessante" reale Anwendungen. P=NPwird viele Konsequenzen haben:

  • Es wird möglich sein, Optimierungsprobleme, die derzeit angenähert sind, genau zu lösen. Dies ist der Fall beim Travelling Salesman Problem und Job Scheduling Problem
  • Es bricht einige Sicherheitsmaßnahmen, die auf der Tatsache beruhen, dass die erforderliche Rechenzeit enorm ist. Beispielsweise basieren viele Verschlüsselungsschemata und Algorithmen in der Kryptographie auf der Faktorisierung von Zahlen, wobei der bekannteste Algorithmus eine exponentielle Komplexität aufweist. Diese Algorithmen werden unbrauchbar, wenn ein Polynomalgorithmus gefunden wird.

Die Quintessenz liegt in der Natur der Probleme, von denen bekannt ist, dass sie NP-vollständig sind. Dies sind nicht nur Probleme, die von wenigen Wissenschaftlern an einem abgelegenen Ort verursacht wurden, um sich gegenseitig zu unterhalten. Sie können in geschäftlichen Begriffen ausgedrückt werden. In der Tat mögen es einige Jobinterviewer, NP-vollständige Probleme in ihren Fragen zu verbergen, um Kandidaten zu testen.

UmNyobe
quelle
3
Die Faktorisierung ganzer Zahlen ist zwar ein schwieriges Problem, es ist jedoch nicht bekannt, dass sie NP-vollständig ist.
Dan_waterworth
4
@dan_waterworth: Es ist nicht bekannt, ob die ganzzahlige Faktorisierung NP-hart ist, aber es ist bekannt, dass es sich um NP handelt. [Oft scheinen die Leute "NP-vollständig" zu sagen, wenn sie "in NP" oder "NP-schwer" meinen. In gewisser Weise wäre es so, als würde jemand in einer Situation, in der "weniger als" genauer wäre, "weniger als oder gleich" sagen.]
Macneil,
5

Diese Möglichkeiten werden in den Fünf Welten von Impagliazzo behandelt .

Hier sind einige Punkte zum Mitnehmen:

  • Künstliche Intelligenz könnte einen riesigen Sprung machen. Wenn zum Beispiel genügend "Trainingsdaten" vorliegen, sind die kürzesten Schaltkreise, um die richtigen Ausgaben aus den Eingaben zu erzeugen, die beste Übersetzungsmethode. Insbesondere würde es trivial werden, eine perfekte Spracherkennung und Sprachübersetzung zu haben. Wenn es sich bei Ihren Trainingsdaten um Filme handelt, die mit dem Oscar ausgezeichnet wurden, können weitere Filme erstellt werden, die mit dem Oscar ausgezeichnet wurden.

  • Algorithmen, wie sie in Schulen gelehrt werden, wären völlig anders. Anstatt so viele verschiedene algorithmische Techniken zu erlernen, konzentrieren sich die Kurse darauf, Probleme auf die Überprüfung der richtigen Antworten zu reduzieren. Dies würde die Programmierung erheblich vereinfachen.

  • Die Wirtschaft würde wesentlich effizienter werden. Es würde Störungen geben, einschließlich der Verdrängung von Programmierern. Beim Programmieren selbst geht es mehr um das Sammeln von Trainingsdaten und weniger um das Schreiben von Code. Google hätte die Ressourcen, um sich in einer solchen Welt zu behaupten.

  • Da die Kryptografie mit öffentlichen Schlüsseln "out" wäre, müsste Amazon Ihnen ein One-Time-Pad auf einem USB-Stick senden, um sichere Transaktionen durchführen zu können.

  • Mathematische Beweise könnten automatisch generiert und verifiziert werden.

Insgesamt würde es eine technologische Singularität einführen; die Implikationen von P = NP wären weitreichend. Außerdem geht Lance Fortnow auf diesen Punkt in einem separaten Blogeintrag ein , den Sie lesen sollten.

Macneil
quelle
-1

Der Nachweis von P = NP würde ein erneutes Interesse an der Suche nach einem Reduktionsalgorithmus beinhalten. Die Leute würden auch versuchen, einige Untergrenzen für die mit dem Reduktionsalgorithmus verbundenen Konstanten zu finden.

Der Nachweis von P = NP wäre nicht so bedeutend wie andere Behauptungen, da dies in Form eines Null-Wissensnachweises erfolgen könnte. Zu wissen, dass P = NP ist, ohne den Reduktionsalgorithmus zu kennen, würde sich kaum von der gegenwärtigen Situation unterscheiden.

Stellen Sie sich vor, jemand hätte bewiesen, dass der Reduktionsalgorithmus existiert, aber O ist (sqrt (n) + 2 ^ 4096).

Emory
quelle
1
Tatsächlich gibt es einen expliziten Reduktionsalgorithmus, der genau dann in P steht, wenn P = NP ist. Es besteht darin, alle möglichen Programme zu durchlaufen und sie parallel auszuführen, bis man die Lösung findet.
Arthur B
@ArthurB faszinierend. Angenommen, P = NP, wie ist die Reihenfolge des Algorithmus?
Emory
Es ist unbekannt, aber es ist die optimale Reihenfolge. scholarpedia.org/article/Universal_search
Arthur B
1
@ArthurB also, wenn P = NP und der Reduktionsalgorithmus O (n ^ 99999999) ist, ist P = NP immer noch so eine große Sache?
Emory