Dies ist der sechste Artikel in einer siebenteiligen Reihe über Algorithmen und Berechnungen, in der untersucht wird, wie wir einfache Binärzahlen verwenden, um unsere Welt mit Energie zu versorgen. Der erste Artikel Wie Algorithmen die Welt steuern, in der wir leben , kann gefunden werden hier .
Wenn wir uns hinsetzen, um ein Problem zu lösen, versuchen nur sehr wenige von uns herauszufinden, welche Art von Problem wir zu lösen versuchen. In fast allen Fällen ist die Antwort auf diese Frage eine interessante Übung und kannin einigen Fällen sogar bei der Lösung des Problems helfen, aber sonst nicht viel. Aber bei so etwas ist die Situation ganz anders. die Problem mit Handlungsreisenden weshalb es so ein Gegenstand des Studiums und der Forschung von theoretischen Informatikern und Mathematikern ist. Es hat alles im Zusammenhang mit der Einstufung als Problem.
Klassifizierungsprobleme: P Vs NP
Probleme, von denen wir einen effizienten Algorithmus kannten, der eine Lösung in Polynomzeit liefern kann, werden klassifiziert als P Probleme - P bedeutet Polynomzeit in diesem Fall. Dies war offensichtlich die erste Untergruppe von Problemen, die wir klassifizieren konnten: Von all diesen Problemen haben wir es zumindest geschafft, diese hier zu lösen. Dinge wie das Sortieren von Listen, das Ausgleichen von Bäumen und das Verschlüsseln von Daten sind allesProbleme, für die wir effiziente Algorithmen haben und die daher zur Teilmenge gehören P .
Später fanden wir eine weitere Untergruppe von Problemen, die P selbst war eine Teilmenge von, NP-Probleme . The NP steht für nichtdeterministische Polynomzeit aber für unsere Zwecke müssen Sie nicht zu viel darüber wissen, was das bedeutet, außer dass es Teil der grundlegenden Informatik der Turing-Ära ist, die jedem einzelnen modernen Computer zugrunde liegt. Was Sie wissen müssen, ist das NP-Probleme Es ist kein Algorithmus bekannt, der ein Ergebnis in der Polynomzeit erzeugen kann.
Wenn Sie jedoch eine Lösung für eine erhalten NP-Problem die Überprüfung der Richtigkeit ist einfach und kann in durchgeführt werden Polynomzeit oder weniger. Wir nutzen diese Tatsache jedes Mal, wenn wir unsere iPhones entsperren oder Nachrichten über WhatsApp senden. Wie sich herausstellt, NP-Probleme sind perfekt für die Verschlüsselung geeignet; es gibt nur einen Weg, um das Problem zu lösen, bei dem die Verschlüsselung schnell entsperrt wird. Sie müssen die Antwort im Voraus haben.
VERBINDUNG: 7 WESENTLICHE ALGORITHMEN, DIE DIE WELT LAUFEN
Natürlich mögen wir Verschlüsselung und wir sind froh, dass sie sicher ist vorerst , aber es gibt viele Probleme in NP für die wir wirklich, wirklich effiziente Algorithmen benötigen. Trotz der besten Bemühungen einiger unglaublich kluger Leute wurden bei der Lösung aller bis auf wenige nur sehr geringe Fortschritte erzielt. NP-Probleme das wissen wir. Dies hat eines der großen ungelösten mathematischen und rechnerischen Probleme der letzten 50 Jahre verursacht : P gegen NP auch genannt P = NP .
Was diese Gleichung verlangt, kann jede gegeben werden NP-Problem in Polynomzeit gelöst werden, also machen NP-Probleme wirklich P Probleme die nur richtig gelöst werden müssen oder da sind NP-Probleme für die in der Polynomzeit keine Lösung gefunden werden kann und daher praktisch unlösbar bleibt, egal welche Algorithmen wir entwickeln?
Wenn Sie sich diese beiden Problemgruppen ansehen, P gegen NP Ziel ist es, eines von zwei Dingen zu beweisen: entweder P = NP was bedeutet, dass insgesamt NP-Probleme als Set - einschließlich derer, die wir kennen und die wir möglicherweise in Zukunft entdecken werden - gehören tatsächlich dazu P und kann in Polynomzeit gelöst werden; oder P ≠ NP und das Unabhängig davon, welchen Algorithmus wir entwickeln, gibt es einen mathematischen Grund für die Zeitkomplexität eines Problems, und dieser Grund ist größer als die Polynomzeit.
Die Antwort auf diese Frage ist so wichtig, dass jeder, der die Antwort findet, vom Clay Mathematics Institute einen Preis in Höhe von einer Million Dollar erhält, ganz zu schweigen von der Installation im Pantheon der Informatik neben John Von Neumann, Alan Turing, Ada Lovelace undandere Leuchten.
Für viele das Problem von P gegen NP geht es hauptsächlich um die Tatsache, dass es eine Lücke in unserem Verständnis von Mathematik gibt, die geschlossen werden muss. Mathematiker und Wissenschaftler aller Disziplinen verabscheuen ein Wissensvakuum, daher ist die Lösung dieses Problems grundsätzlich wichtigsagte, das Streben nach P = NP hat immense Auswirkungen auf die reale Welt, wenn mathematisch bewiesen ist, dass P = NP . Um zu verstehen, warum, müssen wir die letzten beiden Probleme einbringen, die alles zusammenhalten.
NP-hart und NP-vollständig
NP-vollständig ist eine spezielle Kategorie von NP-Probleme die Zeitkomplexitäten aufweisen, die größer als die Polynomzeit sind, in der Polynomzeit überprüfbar sind und zu einer Reihe von Problemen gehören, die als bekannt sind NP-hart . NP-hart Probleme sind im Wesentlichen solche, die mindestens so schwer sind wie die schwersten NP-Problem muss aber nicht in Polynomzeit überprüfbar sein.
Aufzählung aller möglichen Teilmengen der Menge jedes einzelnen Atoms im Universum ist eine NP-hart Problem. Wir können nicht beweisen, dass ein solches Problem in Polynomzeit unlösbar ist, aber es gibt keinen Grund zu der Annahme, dass wir diesen Algorithmus jemals finden oder sogar eine Maschine bauen werden, die leistungsfähig genug ist, um ihn auszuführen, und selbst wenn uns jemand eine Antwort gegeben hat.wir würden nicht einmal anfangen zu wissen, wie man es überprüft.
Ein anderer NP-hart Das Problem besteht darin, einen Schachzug in einem bestimmten Board-Status zu identifizieren, der der absolut beste Zug ist, den Sie machen können. Um dies zu bestimmen, müssen Sie wissen, dass jeder zweite Zug zu einem schlechteren Ergebnis führt und der einzige Weg, dies zu tunWir wissen, wie man bestimmt, dass jeder Verzweigungspfad jeder Bewegung, Gegenbewegung usw. zu folgen ist, was mit der gegebenen Brettposition möglich ist. Sobald Sie das Endergebnis jedes Zweigs dieses praktisch unendlichen Entscheidungsbaums erreicht haben, würden Sie das beste Ergebnis erzielen und sagen, dass dies der beste Schritt war, den Sie hätten machen können.
Wenn Sie mir sagen, dass ein bestimmter Schritt wirklich der bestmögliche Schritt war, den Sie hätten machen können, gibt es für mich keine Möglichkeit, dies schnell zu überprüfen. Ich müsste auf genau denselben Brute-Force-Permutationsalgorithmus zurückgreifen, den Sie gerade verwendet haben, um jede Konsequenz jeder Bewegung zu untersuchen. Die Überprüfung der Lösung würde genau so lange dauern, bis das Problem gelöst ist.
Wenn Ihnen das bekannt vorkommt, liegt das daran, dass es so ist. Dies ist das gleiche Grundproblem wie beim Problem mit Handlungsreisenden was bedeutet, dass es im Wesentlichen um Optimierung geht. Wie sich herausstellt, ist dies eines der bestimmenden Merkmale von NP-vollständig Probleme; Sie versuchen wirklich nur, ein Problem zu lösen, das unzählige Variationen aufweist, und diese Variationen umfassen die Gesamtheit dessen, was wir als wesentliche Geschäfts-, Richtlinien- oder Forschungsentscheidungen betrachten.
Der Algorithmus für alles
Deshalb P = NP wichtig. Wir können es nicht sicher wissen, aber es gibt allen Grund zu der Annahme, dass die Antwort auf diese Frage durchläuft NP-vollständig . Erstens jeder Algorithmus, der eine Lösung für eine zurückgibt NP-vollständig Problem in der Polynomzeit kann geändert werden, um jedes einzelne zu lösen NP-vollständig Problem in der Polynomzeit, da sie im Kern alle das gleiche Problem sind.
Nicht nur das, sondern Teil der Definition von a NP-vollständig Problem ist jedes Problem in NP ist auf jeden reduzierbar NP-vollständig Problem, was bedeutet, dass ein Algorithmus, der löst NP-vollständig in Polynomzeit werden auch alle gelöst NP Probleme auch in der Polynomzeit; mit anderen Worten, Lösen eines NP-vollständig Problem in der Polynomzeit beweist P = NP standardmäßig und effektiv effektiv löst fast alle der schwierigsten Rechenprobleme in der realen Welt buchstäblich über Nacht.
Das macht also im Wesentlichen den Algorithmus, der ein löst NP-vollständig Problem in der Polynomzeit ein Algorithmus für alles. Deshalb P = NP Diese seltsame, undurchsichtig klingende Gleichung ist so vielversprechend, wenn sie sich als wahr erweisen kann und der einzige wirkliche Weg, dies zu tun, darin besteht, eine zu lösen. NP-vollständig Problem in der Polynomzeit. Dieser Algorithmus würde zu einem Algorithmus werden, der in einem Augenblick eine völlig andere Welt freischalten könnte. Die Möglichkeit des Quantencomputers ist sehr aufregend, gerade weil dies unsere beste Chance zur Lösung ist. NP-vollständig in der Polynomzeit bleibt jedoch abzuwarten, ob dies möglich ist oder nicht.
Der letzte Artikel in unserer Reihe über Algorithmen und Berechnungen Quantenalgorithmen und die Zukunft des postklassischen Rechnens , kann gefunden werden hier