P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (2024)

Eintauchen in die berüchtigtste offene Frage der Informatik und ihre weitreichenden philosophischen Konsequenzen.

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (1)

Seit den Anfängen der Geschichte war der Mensch eine Problemlöserspezies. Von der frühen Landwirtschaft bis zur Erforschung des Weltraums scheint die Lösung mathematischer Probleme ein entscheidender Faktor für das Überleben des Menschen zu sein. Seit den 70er Jahren sind einige Rechenprobleme, deren Lösung früher mühsam war, in Sekundenbruchteilen lösbar geworden, hauptsächlich aufgrund des exponentiellen Wachstums der Verarbeitungsleistung. Einige einzigartige Probleme bleiben jedoch dem technologischen Fortschritt gleichgültig, da selbst bei den leistungsstärksten Computern die Lösung länger dauert als ein menschliches Leben, selbst wenn das Problem in einem vernünftigen Ausmaß liegt. Tatsächlich beruht die moderne Verschlüsselung auf der Tatsache, dass es praktisch unmöglich ist, das Produkt großer Primzahlen zu faktorisieren. Diese Probleme scheinen eine gemeinsame Schwierigkeit zu haben, die im Zentrum des P-gegen-NP-Rätsels steht - Was ist machbar und was ist effektiv unmöglich?

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (2)

1859 illustrierte der irische Mathematiker William Hamilton ein mathematisches Spiel namens Icosian . Dieses Spiel wurde auf einer hölzernen Dodekaederoberfläche gespielt, die aus 20 Ecken (Eckpunkten) besteht. Jede dieser Ecken war mit dem Namen einer Stadt beschriftet. Das Ziel des Spiels war es, einen Zyklus zu finden, der jeden Scheitelpunkt genau einmal besucht und dann zum Ausgangspunkt zurückkehrt. Diese Art von Pfad wird als Hamilton-Zyklus bezeichnet. Dieses einfache Spiel brachte ein bedeutendes Problem in der Graphentheorie hervor, das sich The Hamiltonian Cycle Decision Problem nennt. Wie können wir bei einem beliebigen Graphen wissen, ob es einen Hamiltonian Cycle enthält?

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (3)

Bestimmen Sie anhand eines Diagramms, ob es einen Hamilton-Zyklus enthält.

Ein Ansatz zur Lösung dieses Problems besteht darin, einen möglichen Pfad im Diagramm zu durchlaufen und zu überprüfen, ob der Pfad ein Hamilton-Zyklus ist. Da die Anzahl der möglichen Pfade jedoch bis zu n! Erreichen kann , enthält selbst ein Diagramm mit nur 40 Eckpunkten möglicherweise mehr als Quattuordecillion (10⁴⁵) -Pfade, sodass das Problem selbst für die leistungsstärksten Prozessoren in angemessener Zeit kaum zu lösen ist . Selbst wenn es uns irgendwie gelingt, einen Superprozessor zu erstellen, der diese Berechnung aufgrund der faktoriellen Abhängigkeit zwischen der Anzahl der Scheitelpunkte und der Anzahl der Pfade bewältigen kann , würde selbst die geringste Hinzufügung von Scheitelpunkten zum Diagramm eine radikale Erhöhung erfordern Rechenleistung. Wir können sagen, dass die radikale Natur des faktoriellen Wachstums dieses Problem schwieriger macht als andere Probleme. Dies ist die Intuition hinter der Härte mathematischer Probleme - Ein Problem wird als schwieriger angesehen, wenn die zur Lösung erforderlichen Ressourcen radikal zunehmen, wenn die Eingabe zunimmt.

Um diese Idee zu formalisieren, verwenden Informatiker die Skala der Zeitkomplexität. Die zeitliche Komplexität bezieht sich darauf, wie viele Schritte zur Lösung eines Problems erforderlich sind und wie sich die Anzahl der erforderlichen Schritte mit der Größe des Problems erhöht. Bei einem gegebenen Algorithmus wird die Zeitkomplexität des Algorithmus als asymptotische Funktion beschrieben , die von der Eingabegröße des Algorithmus abhängt. Es wird verwendet, um Algorithmen danach zu klassifizieren, wie ihre Anzahl von Schritten oder ihr Platzbedarf mit zunehmender Eingabegröße zunimmt.

"Der asymptotische Standpunkt ist der Theorie der rechnerischen Komplexität inhärent und zeigt Strukturen auf, die durch eine endliche, präzise Analyse verdeckt würden."

- Avi Wigderson

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (4)

Grundsätzlich unterscheidet man zwischen Algorithmen gemacht , die eine haben Polynomzeit Komplexität , wo ihre Komplexität Funktion ist ein Polynom , zu denen , die eine radikalere Komplexität Funktion haben. Diese Unterscheidung wird hauptsächlich getroffen, weil das Polynomwachstum als moderater als andere angesehen wird , in dem Sinne, dass große Änderungen der Eingabegröße keine radikale Zunahme der erforderlichen Schritte verursachen würden. Ein Polynom ist ein Konstrukt, das nur die Operationen Addition, Subtraktion, Multiplikation und nicht negative ganzzahlige Exponenten umfasst und daher niemals ein exponentielles oder ein faktorielles Wachstum einführt. Die Wahl der Polynomzeit zur Darstellung einer effizienten Berechnung scheint willkürlich; es hat sich jedoch im Laufe der Zeit aus vielen Perspektiven gerechtfertigt. Zum Beispiel bewahrt das Schließen von Polynomen unter Addition, Multiplikation und Zusammensetzung den Begriff der Effizienz unter natürlichen Programmierpraktiken, wie das Verketten von Programmen zu einer Sequenz oder das Verschachteln eines Programms innerhalb eines anderen Programms.

Algorithmen mit einer Polynomzeitkomplexität werden als „effizient“ bezeichnet.

Im Laufe der Jahre gab es viele Versuche, das Hamiltonian Cycle Decision Problem effizient zu lösen. Einer davon ist der Held-Karp-Algorithmus , der es schafft, dieses Problem in exponentieller Zeit zu lösen. Dennoch kann kein bekannter Algorithmus dieses Problem in der Polynomzeit lösen, und daher wird es immer noch als schwieriges Problem angesehen .

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (5)

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (6)

Es tritt jedoch ein interessantes Phänomen auf: Obwohl wir dieses Problem bei einem Pfad im Diagramm nicht effizient lösen können, können wir zumindest effizient prüfen, ob es sich um einen Hamilton-Zyklus handelt - da die maximale Anzahl von Eckpunkten in einem einfachen Zyklus n beträgt Dann ist die zum Durchlaufen eines Pfades erforderliche Zeit polynomiell auf n begrenzt .

Dieses Phänomen tritt in anderen schwierigen Problemen, wie die Sudoku Entscheidung Problem - Bei einer unvollständigen Sudoku, wir wollen wissen , ob es mindestens eine gültige Lösung. Jede vorgeschlagene Sudoku-Lösung kann leicht überprüft werden, und die Zeit zum Überprüfen einer Lösung verlängert sich polynomiell, wenn das Raster größer wird. Alle bekannten Algorithmen zum Finden von Lösungen benötigen jedoch für schwierige Beispiele Zeit, die exponentiell wächst, wenn das Gitter größer wird. Ähnlich wie beim Hamiltonian Path-Entscheidungsproblem ist kein Algorithmus bekannt, der das Sudoku-Entscheidungsproblem effizient lösen kann, aber bei einer gegebenen Lösung könnte die Lösung effizient verifiziert werden. Es scheint, dass viele andere Entscheidungsprobleme diese Eigenschaft teilen - Unabhängig davon, ob sie effizient gelöst werden können, können ihre vorgeschlagenen Lösungen effizient überprüft werden. Diese Gruppe von Problemen wird als NP definiert .

Ein Entscheidungsproblem liegt in NP vor, wenn seine Lösungen effizient überprüft werden können.

Das Akronym NP steht für nichtdeterministische Polynomzeit (trotz der allgemeinen Überzeugung, dass NP „nicht P“ bedeutet).

Wenn wir weiter über die Beziehung zwischen der Lösbarkeit eines Problems und der Überprüfbarkeit seiner Lösungen nachdenken, kommen wir zum nächsten Punkt: Wenn ein Entscheidungsproblem effizient lösbar ist, müssen seine Lösungen effizient überprüfbar sein. Warum? Denn wenn ein Entscheidungsproblem effizient lösbar ist, können wir seine Lösungen effizient finden. Wenn eine vorgeschlagene Lösung vorliegt, können wir sie einfach überprüfen, indem wir sie mit den tatsächlichen Lösungen des Problems vergleichen. Anders ausgedrückt, die Richtigkeit des Algorithmus, der die Lösung generiert, bestätigt diese Lösung automatisch. Aus dieser Schlussfolgerung ist ersichtlich, dass NP - die Menge aller Entscheidungsprobleme, bei denen ihre Lösungen effizient überprüfbar sind, eine Teilmenge von Problemen enthält, die auch effizient lösbar sind. Diese Teilmenge ist als P definiert.

P ist die Menge aller Entscheidungsprobleme, die effizient lösbar sind. P ist eine Teilmenge von NP.

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (7)

Das Hamiltonian Path Decision Problem verfügt über einen effizienten Algorithmus, der seine Lösungen überprüfen kann. daher ist es in NP. Man kann sich fragen, ob dieses Problem in P liegt. Einerseits gibt es kein Wissen über einen effizienten Algorithmus, der dieses Problem löst. Andererseits gibt es keinen Beweis dafür, dass ein solcher Algorithmus nicht existiert. Tatsächlich besteht immer noch die Möglichkeit, dass ein solcher Algorithmus existiert und noch nicht entdeckt wurde. Gleiches gilt für das Sudoku-Entscheidungsproblem und in der Tat für viele andere Hauptprobleme, einschließlich des Booleschen Erfüllbarkeitsproblems , des Problems des Handlungsreisenden , des Subset-Summenproblems , des Clique-Problems , des Graph-Farbproblems und anderer - auch wenn Wir haben bewiesen, dass diese Probleme in NP liegen. Es gibt keinen Beweis dafür, dass sie außerhalb von P liegen. Genau darum geht es bei der P = NP-Frage:

Sind P und NP tatsächlich gleich? Wenn ja, bedeutet dies, dass alle Probleme in NP effizient gelöst werden können, obwohl wir die mysteriösen Algorithmen, die dies erreichen, noch nicht gefunden haben. Andernfalls gibt es Probleme in NP, die nicht effizient gelöst werden können, und jeder Versuch, dies zu tun, würde eine völlige Verschwendung unserer Zeit und Anstrengungen bedeuten.

In den meisten Fällen ist es negativ, Probleme nicht effizient lösen zu können. In einigen Fällen können wir jedoch von der „Härte“ eines Problems profitieren. Das Hauptmerkmal von Problemen, die in NP und nicht in P auftreten, ist, dass es schwierig ist, sie zu lösen, aber ihre Lösungen leicht zu überprüfen. Diese Art von Asymmetrie ist besonders im Bereich der Kryptographie nützlich - Informationen können hinter einem schwierigen Problem „eingeschlossen“ werden. Jeder Brute-Force-Angriff würde die Informationen nicht in angemessener Zeit freischalten, während Vorkenntnisse über die Lösung (ein „Schlüssel“) effizient überprüft werden könnten und daher den Zugriff ermöglichen würden. Das bekannteste Beispiel für dieses Konzept ist das RSA-Kryptosystem mit öffentlichem Schlüssel , das auf dem Prime Factorization Problem basiert .

Entscheiden Sie bei zwei positiven ganzen Zahlen n und k, ob n einen Primfaktor kleiner als k hat.

- Das Hauptentscheidungsentscheidungsproblem

Es ist bekannt, dass dieses Problem in NP auftritt, da seine Lösungen effizient verifiziert werden können: Bei einer gegebenen ganzen Zahl c dauert es eine Polynomzeit, um zu wissen, ob c eine Primzahl kleiner als k und ein Faktor von n ist. Kein bekannter Algorithmus kann dieses Problem jedoch in der Polynomzeit lösen. Daher ist es unter Verwendung von zwei beträchtlich großen Primzahlen möglich, ihre Multiplikation zu berechnen, die zum Erzeugen eines öffentlichen und eines privaten Schlüssels verwendet wird . Der öffentliche Schlüssel ist jedem bekannt und wird zum Verschlüsseln von Nachrichten verwendet. Mit dem öffentlichen Schlüssel verschlüsselte Nachrichten können mit dem privaten Schlüssel nur in angemessener Zeit entschlüsselt werden, vorausgesetzt, es gibt keine effiziente Möglichkeit, eine große Ganzzahl in ihre Primfaktoren zu zerlegen .

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (8)

Allerdings , wenn P NP =, dann die letzte Annahme ist falsch. Warum? Wenn P gleich NP ist, liegt das Hauptfaktorisierungsproblem in P, was bedeutet, dass es effizient gelöst werden kann. Sobald ein solcher Algorithmus gefunden ist, kann jeder öffentliche Schlüssel in angemessener Zeit entschlüsselt werden, ohne dass ein privater Schlüssel erforderlich ist, wodurch das gesamte RSA-Kryptosystem zumindest im theoretischen Sinne vollständig anfällig wird.

Die negativen Seiten von P, die gleich NP sind, sind jedoch im Vergleich zu den potenziellen Vorteilen, die es bietet, relativ unbedeutend. Es gibt buchstäblich Tausende von NP-Problemen in Mathematik, Optimierung, künstlicher Intelligenz, Biologie, Physik, Wirtschaft und Industrie, die auf natürliche Weise aus unterschiedlichen Erfordernissen entstehen und deren effiziente Lösungen uns auf vielfältige Weise zugute kommen. Der Beweis, dass P = NP ist, würde bedeuten, dass all diese schwierigen Probleme in einer Polynomzeit gelöst werden können, was zu einer massiven intellektuellen Verfolgung nach diesen bemerkenswerten Algorithmen führen würde. Einmal enthüllt, würden diese Algorithmen möglicherweise den menschlichen Fortschritt weit außerhalb unserer Reichweite fördern.

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (9)

Selbst solche Konsequenzen können im Vergleich zur Revolution zu einer Bedeutungslosigkeit verblassen, die eine effiziente Methode zur Lösung von NP-Problemen in der Mathematik selbst verursachen würde .

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (10)

Betrachten Sie als Beispiel den bekannten Satz von Pythagoras , der die Beziehung a² + b² = c² zwischen den Beinen und die Hypotenuse eines rechtwinkligen Dreiecks angibt . Dieser Satz hat 370 bekannte Beweise . Jeder dieser Beweise ist eine mögliche Lösung für das folgende Entscheidungsproblem : „Ist der Satz von Pythagoras korrekt?“. Diese Idee kann verallgemeinert werden:

Wenn T ein Theorem ist und p sein Beweis ist, dann ist p eine Lösung für das Entscheidungsproblem: "Ist T richtig?"

Diese Beziehung zwischen mathematischen Theoremen und Entscheidungsproblemen ermöglicht es uns, die Diskussion über P gegenüber NP zu verallgemeinern. Wenn die Richtigkeit eines Beweises in Polynomzeit überprüft werden kann, liegt das entsprechende Entscheidungsproblem in NP (da der Beweis eine vorgeschlagene Lösung für diese Entscheidung ist Problem). In einer Welt, in der P gleich NP ist, liegt ein solches Entscheidungsproblem in P, was bedeutet, dass es in Polynomzeit gelöst werden kann. Die Lösung eines solchen Entscheidungsproblems besteht im Wesentlichen darin, Beweise für Satz T zu finden. Dies könnte bis zu einem gewissen Grad bedeuten, dass der Nachweis eines mathematischen Satzes nicht wesentlich schwieriger ist als die Überprüfung der Richtigkeit eines gegebenen Beweises.

P gleich NP kann bedeuten, dass der Nachweis eines mathematischen Theorems nicht grundsätzlich schwieriger ist als die Überprüfung der Richtigkeit seines Beweises.

Die letzte Schlussfolgerung ist wirklich bemerkenswert, wenn man bedenkt, dass jeder mathematische Beweis in eine Reihe klar definierter logischer Aussagen umgewandelt werden kann, die von einem Computerprogramm verarbeitet werden können, um diesen Beweis automatisch zu überprüfen. Daher würde P gleich NP bedeuten, dass der Nachweis mathematischer Theoreme durch ein einfaches Computerprogramm erfolgen kann.

"P gleich NP würde die Mathematik transformieren, indem es einem Computer ermöglicht würde, einen formalen Beweis für jeden Satz zu finden, der einen Beweis von angemessener Länge hat, da formale Beweise in Polynomzeit leicht erkannt werden können."

- Stephen Cook

Ein psychologischer Grund, warum Menschen P = NP für unwahrscheinlich halten, ist, dass Aufgaben als Beweis mathematischer Theoreme oft ein gewisses Maß an Kreativität erfordern , das wir von einem einfachen Computerprogramm nicht erwarten.

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (11)

„Wir bewundern Wiles 'Beweis von Fermats letztem Theorem, die wissenschaftlichen Theorien von Newton, Einstein, Darwin, Watson und Crick, den Entwurf der Golden Gate Bridge und der Pyramiden und manchmal sogar Hercule Poirots und Miss Marples Analyse eines Mordes genau weil sie einen Sprung erfordern, der nicht von jedem gemacht werden kann, geschweige denn von einem einfachen mechanischen Gerät. “

- Avi Wigderson

Der obige Punkt führt uns zu einer Diskussion über die Natur des menschlichen Gehirns. Während die Wissenschaft weit davon entfernt ist, den Mechanismus des Gehirns zu verstehen, bestimmen die Gesetze der Physik sein Verhalten. Als solches und wie jeder andere natürliche Prozess ist das Gehirn ein effizientes Rechengerät. Daher wurde jede Lösung für jedes Problem, das vom Gehirn erkannt wurde, per Definition effizient erkannt . Daher kann P gleich NP bedeuten, dass das Gehirn in der Lage ist , diese Probleme mit der gleichen Effizienz zu lösen.

"Wenn P = NP wäre, hätte jeder Mensch oder Computer die Art von Argumentationskraft, die traditionell Gottheiten zugeschrieben wird, und dies scheint schwer zu akzeptieren."

- Avi Wigderson

Die Idee, mit der erstaunliche Entdeckungen wie Wiles 'Beweis von Fermats letztem Satz oder Einsteins Relativitätstheorie von einem gedankenlosen Roboter erzeugt werden könnten, ist für die meisten Menschen nicht intuitiv, da sie eine starke Meinung teilen, nach der Kreativität für das Erreichen solcher Einsichten unbedingt erforderlich war.

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (12)

„Wenn P = NP, dann wäre die Welt ein völlig anderer Ort, als wir normalerweise annehmen. Jeder, der eine Symphonie schätzen könnte, wäre Mozart. “

- Scott Aaronson

Komplexitätstheoretiker glauben im Allgemeinen, dass P nicht gleich NP ist und eine so schöne Welt nicht existieren kann. Im Jahr 2000 nannte das Clay Math Institute das P- gegen- NP- Problem als eine der sieben wichtigsten offenen Fragen in der Mathematik und hatte einen Millionen-Dollar-Preis für einen Beweis angeboten, der bestimmt, ob P = NP ist oder nicht .

🎗 Weitere Informationen finden Sie in meinem Blog .

P vs. NP - Was ist der Unterschied zwischen dem Lösen eines Problems und dem Erkennen seiner Lösung? (2024)
Top Articles
Latest Posts
Article information

Author: Margart Wisoky

Last Updated:

Views: 5406

Rating: 4.8 / 5 (58 voted)

Reviews: 81% of readers found this page helpful

Author information

Name: Margart Wisoky

Birthday: 1993-05-13

Address: 2113 Abernathy Knoll, New Tamerafurt, CT 66893-2169

Phone: +25815234346805

Job: Central Developer

Hobby: Machining, Pottery, Rafting, Cosplaying, Jogging, Taekwondo, Scouting

Introduction: My name is Margart Wisoky, I am a gorgeous, shiny, successful, beautiful, adventurous, excited, pleasant person who loves writing and wants to share my knowledge and understanding with you.