Die Überprüfung ist einfacher als das Finden?
Es sollte schwieriger sein, eine Lösung für ein Problem zu finden, als zu überprüfen, ob eine Lösung richtig ist. Das scheint offensichtlich, wenn Sie jemals ein Sudoku-Rätsel gelöst oder einen Zauberwürfel gelöst oder eine Partie Schach gespielt haben. Aber diese Aussage, so intuitiv sie auch sein mag, führt uns direkt zu einer der tiefsten mathematischen Fragen unserer Zivilisation.
Nicht-deterministische Polynomzeit (oder NP) Probleme sind solche, bei denen Sie leicht überprüfen können, ob eine Antwort korrekt ist., Im Gegensatz dazu sind Polynomzeit (oder P) Probleme diejenigen
, bei denen das Finden der Antwort einfach ist. Wenn Sie die Antwort finden können, haben Sie sie als korrekt überprüft, sodass jedes Problem in P auch in NP liegt. Wir sagen P ist eine Unterklasse von NP. Wir wissen jedoch nicht, ob es ein bestimmtes Problem in NP gibt, das nicht in P ist, und das nennen wir das P vs NP Problem.
Das P vs NP-Problem ist eines der zentralen ungelösten Probleme in Mathematik und theoretischer Informatik. Es gibt sogar einen Clay Millennium Prize, der eine Million Dollar für seine Lösung anbietet., Es gibt jedoch wahrscheinlich viel einfachere Möglichkeiten, Millionär zu werden, als P vs NP zu lösen!
Kürzlich gab es ein Summen, als jemand vorgab, es auf arXiv zu lösen, obwohl schnell eine Lücke im Beweis gefunden wurde. Angesichts des jüngsten Interesses an dem Problem und seines zentralen Platzes in der Mathematik diskutiere ich es im Blog dieser Woche.
Sudoku
Wenn Sie ein ausgefülltes Sudoku-Puzzle in einer Zeitung erhalten, können Sie es in den Papierkorb werfen. Wenn Sie möchten, können Sie jedoch die Zeilen, Spalten und 3 x 3 Zellen durchsuchen, um festzustellen, dass es sich um eine gültige Lösung handelt: Jede von 1 , 2,…, 9 muss genau einmal vorkommen., Dies ist analog zu NP, da es relativ einfach ist zu überprüfen, ob eine Lösung korrekt ist.
Wenn ich Ihnen jedoch ein teilweise gefülltes Sudoku-Puzzle gebe, kann es schwierig sein, die Lösung zu finden. Das ist die Freude und Herausforderung dieser Art von puzzle. In NP zu sein scheint also nicht sofort zu implizieren, dass das Problem leicht zu finden ist. Diese Intuition steht im Mittelpunkt des P vs NP-Problems.
Präzise Formulierung
Um P und NP genauer zu verstehen, müssen wir Algorithmen besser verstehen und ihre Geschwindigkeit messen. Probleme werden mit einigen festen Eingaben und Ausgaben entweder JA oder NEIN gestellt. Die Eingabe ist eine gegebene Länge, sagen wir n, wobei n eine positive Ganzzahl ist. Dies stellt die Anzahl der Bits dar, die zum Ausdrücken der Eingabe benötigt werden. Ein Algorithmus ist eine Methode oder ein Verfahren zur Lösung eines Problems. Algorithmen geben bei jedem Schritt einer Berechnung Anweisungen und müssen beendet werden., Die Schritte können Sekunden, Millisekunden oder ein anderes festes Zeitintervall sein, das von Ihrem Problem abhängt.
Die Komplexität eines Problems ist die minimale Worst-Case-Laufzeit über alle möglichen Algorithmen, die das Problem in Abhängigkeit von der Länge der Eingabe lösen. Mit anderen Worten, es misst, wie lange es dauert, um das Problem mit dem schnellsten Algorithmus, aber mit der Worst-Case-Eingabe zu lösen.
Ein Problem ist in der Polynomzeit lösbar, wenn bei einer Eingabe der Länge n die Komplexität oben durch die Polynomfunktion nm für eine nicht negative Ganzzahl m begrenzt ist., Die Menge aller Probleme, die in Polynomzeit lösbar sind, wird mit P
In P bedeutet das nicht unbedingt, dass das Problem machbar ist. Zum Beispiel, wenn es n1000 Schritte dauert, um den Algorithmus auszuführen, dann wird es hoffnungslos langsam sein, auch für kleine n. Nicht-deterministische Polynom (oder NP) Probleme sind solche, bei denen Sie überprüfen können, ob die JA-Antwort in Polynomzeit korrekt ist.
NP-Härte
Ein Problem ist NP–hart, wenn ein Polynom-Zeit-Algorithmus dafür einen Polynom-Zeit-Algorithmus für jedes Problem in NP implizieren würde. Wenn also ein NP-Hard-Problem in P wäre, dann ist P = NP., Die NP-schwere Probleme sind mindestens so schwer wie jedes problem in NP. Ein NP-vollständiges Problem ist eines, das NP-hard und in NP ist.
Ein klassisches NP-vollständiges Problem besteht darin, einen Hamilton-Zyklus zu finden. Angenommen, wir haben ein Straßennetz von Städten. Das Problem ist, jede Stadt mit Straßen zu besuchen (keine Flugzeuge erlaubt!) und zurück zum Start. Dies scheint für eine kleine Anzahl von Städten einfach zu sein, aber wenn Sie Hunderte von ihnen erhalten, wird es schwierig., Tausende anderer solcher NP-kompletter Probleme sind bekannt, die sich in der Graphentheorie, Zahlentheorie, Geometrie und anderen Bereichen der Mathematik und Informatik ergeben.
Was ist die Antwort, richtig?
Wenn ich Wetten, dann würde ich davon ausgehen, dass P nicht gleich NP ist, und ich denke, die meisten Experten würden Zustimmen. Wir müssten schrecklich dumm sein, nicht zu sehen, wie all die Tausenden von NP-Complete-Problemen keinen Polynomzeitalgorithmus haben. Aber als Spezies ist Dumm unsere Standardposition, so dass niemand mit 100% iger Sicherheit sagen kann, was die Antwort ist.,
Das Interessante am P vs NP-Problem ist, dass es darauf hinweist, wie begrenzt unser Verständnis ist, wenn wir beweisen, dass bestimmte Probleme keine schnellen Lösungen haben. Dies ist Teil eines größeren Themas auf dem Gebiet der Computational Complexity Theory, das Dutzende anderer Komplexitätsklassen untersucht. Schauen Sie sich die Komplexität Zoo für eine Auflistung dieser Klassen. Zum größten Teil ist es offen, verschiedene (oft exotisch klingende) Komplexitätsklassen anzuzeigen, die richtige Unterklassen voneinander sind. Zum Beispiel ist nicht bekannt, ob NL eine richtige Unterklasse von P ist, und wir wissen nicht, ob FPT eine richtige Unterklasse von W ist.,
Unabhängig von seiner Richtigkeit wird das P vs NP-Problem wahrscheinlich noch einige Zeit offen bleiben. Es sei denn, es ist bewiesen, dass P = NP, Sudoku sicher bleibt.
Anthony Bonato