Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
P vs. NP: Das MILLIONEN Dollar PROBLEM der Informatik
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 106 Zeilen
- Die Informatik ist ein Fachgebiet, das die Art und Weise, wie wir leben und arbeiten, revolutioniert hat.
- Das stimmt immer wahrscheinlich alle zu. Von Smartphones über soziale Medien bis hin zu selbstfahrenden Autos.
- Die Informatik hat die moderne Welt ziemlich entscheidend mitgeprägt. Und im Mittelpunkt steht immer wieder die Frage der Effizienz.
- Wie können wir Algorithmen und Datenstrukturen entwerfen, die es uns ermöglichen, Probleme so schnell und so genau wie möglich zu lösen?
- Und daraus resultiert eine der ältesten und wichtigsten Fragen der Informatik. Das sogenannte P vs.
- NP Problem. Bei diesem Problem geht es um die Frage, ob es möglich ist, Probleme effizient zu lösen,
- die effizient verifiziert werden können oder nicht. Mit anderen Worten, wenn eine Lösung für ein Problem schnell und einfach überprüft
- werden kann, gibt es dann einen Weg, diese Lösung ebenso schnell und einfach zu berechnen. Um das P vs.
- NP Problem zu verstehen, müssen wir zunächst definieren, was wir eigentlich mit effizient meinen.
- In der Informatik wird der Begriff polynomielle Zeit häufig verwendet, um Algorithmen zu beschreiben, die ein Problem in einer Zeit lösen können, die proportional zu einer
- polynomiellen Funktion der Größe der Eingabe ist. Krass kompliziert formuliert, sage ich euch gleich, wie ich das meine.
- Also beispielsweise ein Algorithmus, der eine Liste von n Zahlen in O von n hoch 2 Zeit sortieren kann, der gilt als polynomiell.
- Während ein Algorithmus, der eben O von 2 hoch n Zeit zur Lösung des selben Problems benötigt, der gilt nicht mehr als polynomial Zeit.
- O von 2 hoch n gilt als exponentielle Laufzeit und ist eigentlich, und das ist das Problem, schon bei relativ kurzen Eingaben nicht mehr durchführbar.
- Ist meine Liste 10 Einträge lang, würde ein Algorithmus in O von n hoch 2 beispielsweise 100 Operationen brauchen, ein exponentieller Algorithmus ungefähr 1000.
- Die Klasse der Probleme, die in polynomial Zeit gelöst werden können, wird als P oder die Klasse der einfachen Probleme bezeichnet.
- Die Klasse der Probleme, die in polynomial Zeit verifiziert werden können, wird dagegen als NP oder als Klasse der harten Probleme bezeichnet.
- Einige Beispiele für NP-Probleme sind das Travelling Salesman Problem, das Rucksack oder Knapsack Problem und das Buhl'sche Erfüllbarkeitsproblem.
- Nehmen wir uns kurz nochmal das letzte. Als Beispiel schauen wir uns mal dieses NP-vollständige Problem, das Buhl'sche Erfüllbarkeitsproblem
- genauer an, auch SAT-Problem übrigens genannt. Bei diesem Problem geht es um die Frage, ob es eine Menge von Buhl'schen Variablen, also
- Wahrheitsvariablen gibt, die eine gegebene Buhl'sche Formel erfüllen können. Zum Beispiel ist die Formel in Klammern A oder B und nicht A oder C erfüllt, wenn A
- falsch ist und B und C wahr sind. Das SAT-Problem ist bekanntermaßen NP-vollständig.
- Selbst wenn wir dieses Problem in Polynomialzeit lösen können, können wir jedes Problem in NP in Polynomialzeit lösen.
- Löst du eins in Polynomialzeit, löst du also eigentlich alle. Beim P vs. NP Problem geht es aber nicht um ein Problem insgesamt, sondern um die Frage,
- ob P und NP dieselbe Klasse von Problemen sind oder nicht. Mit anderen Worten, kann jedes NP-Problem, das wir kennen, in Polynomieller Zeit gelöst
- werden. Wenn die Antwort auf diese Frage Ja lautet, dann wäre es möglich, viele schwierige Probleme,
- die derzeit als unlösbar gelten, wie eben das SAT-Problem, effizient zu lösen. Lautet die Antwort hingegen Nein, dann gibt es einige Probleme, die grundsätzlich schwieriger
- zu lösen sind als andere und wir müssen uns nach neuen Problemlösungsmöglichkeiten umschauen.
- Die Frage P vs. NP gilt als eines der Probleme, für deren Lösung es eine Million Dollar gibt.
- Die sind zwar offiziell von keiner Firma ausgeschrieben, aber wenn ihr das wirklich schaffen solltet, könnt ihr euch gewiss sein, dass ihr mindestens diese Summe verdient und
- euer Gehalt sich verzickfacht. Man geht derzeit davon aus, dass P nicht gleich NP ist.
- Aber man weiß es nicht sicher. Man hat keinen Beweis dafür.
- Eine Antwort hätte weitreichende Folgen, nicht nur für die Informatik. Das P vs.
- NP Problem steht in engem Zusammenhang mit der Komplexitätstheorie, die sich mit den zur Lösung von Problemen erforderlichen Ressourcen befasst.
- Wenn P nicht gleich NP ist, dann hat das Konsequenzen für viele andere Bereiche der Mathematik, einschließlich Algebra, Zahlentheorie und Kombinatorik.
- Es würde bedeuten, dass viele Probleme, die derzeit als unlösbar gelten, wie zum Beispiel die Faktorisierung großer ganzer Zahlen, wirklich nicht effizient gelöst werden können.
- Das heißt, wir werden das nie mit unseren Rechnern effizient tun können. Viele kryptographische Protokolle beruhen auf genau dieser Annahme, dass bestimmte Probleme
- eben schwer zu lösen sind. Zum Beispiel eben die Faktorisierung großer Zahlen.
- Wenn P aber gleich NP ist, dann können wir diese Probleme effizient lösen. Was im Endeffekt viele kryptographische Protokolle, mit denen ihr auch gerade auf diese Website
- hier zugreift, angreifbar machen könnten. Wenn P allerdings nicht gleich NP ist, dann kann es möglich sein, kryptographische Protokolle
- zu entwickeln, die wirklich gegen alle möglichen Angriffe bewiesen sicher sind. Das haben wir aktuell noch nicht.
- In der Physik übrigens auch. Das P vs.
- NP Problem hängt mit der Frage zusammen, ob das Universum von einem klassischen Computer, so wie wir ihn gerade benutzen, effizient simuliert werden kann oder nicht.
- Wenn P gleich NP ist, könnte es möglich sein, die Quantenmechanik effizient zu simulieren. Was, wie ihr euch vorstellen könnt, ziemliche Auswirkungen auf Bereiche wie die Materialwissenschaft
- und die Entdeckung von Medikamenten haben kann. Wenn P allerdings nicht gleich NP ist, kann es sein, dass die Simulation des Universums
- Ressourcen oder Berechnungsmöglichkeiten erfordert, die die Möglichkeiten eines klassischen Computers wirklich übersteigen.
- Eventuell also durch Quantencomputer vielleicht lösbar sind? Das P vs.
- NP Problem wurde auch in anderen Bereichen untersucht, unter anderem in der Philosophie und den Wirtschaftswissenschaften.
- In der Philosophie hängt das Problem mit der Frage zusammen, ob moralische Wahrheiten allein durch die Vernunft entdeckt werden können oder nicht.
- Fragt mich bitte nicht wie, da bin ich ein bisschen raus. Wenn das jemand weiß, gerne in die Kommentare schreiben.
- In den Wirtschaftswissenschaften bezieht sich das Problem auf die Frage, ob Märkte Ressourcen effizient zuweisen können oder nicht.
- Okay, hier sind einige der wichtigsten Ansätze, die verwendet wurden, um solche Probleme anzugehen. Eine Möglichkeit, sich dem P vs.
- NP Problem zu nähern, besteht darin, Brute-Force-Algorithmen zu verwenden, um NP vollständige Probleme zu lösen.
- Diese Algorithmen probieren dann einfach alle Lösungen für ein Problem aus, bis sie eine korrekte Lösung gefunden haben.
- Während der Ansatz für Kleininstanzen eines Problems funktionieren kann, wird er für Größeinstanzen einfach völlig unausführbar.
- Die brauchen viel zu lang. Brute-Force-Algorithmen sind zwar in der Lage, diese NP vollständigen Probleme zu lösen,
- aber eben wahnsinnig ineffizient. Am Beispiel unseres SAT-Problems von vorhin.
- Ich muss alle Möglichkeiten, also alle Variablenbelegungen, komplett ausprobieren, um herauszufinden, ob sie die Gleichung lösen oder nicht.
- Ein anderer Ansatz besteht darin, Algorithmen zu entwickeln, die NP vollständige Probleme in polynomialer Zeit lösen können.
- Oder eben effiziente Datenstrukturen zu entwickeln, die das Lösen dieser Probleme überhaupt erst ermöglichen.
- Viele Forscher haben genau diesen Ansatz extrem lang ausprobiert, aber bisher konnte noch niemand beweisen, dass wirklich alle NP vollständigen Probleme effizient gelöst werden können.
- Und manche saßen da wirklich Jahrzehnte dran. Ein dritter Ansatz besteht darin, probabilistische Algorithmen oder randomisierte Algorithmen
- zur Lösung NP vollständiger Probleme zu finden. Diese Algorithmen machen sich den Zufall zunutze, um Berechnungen zu beschleunigen und haben
- sich bei der Lösung vieler schwieriger Probleme tatsächlich schon bewährt. Seither gibt es tatsächlich eine neue Komplexitätsklasse, die Klasse RP, wo es einen polynomiellen Algorithmus
- gibt, der ein Problem löst und eben dabei zur Lösung Zufall verwendet. Es ist jedoch nicht klar, ob diese Algorithmen zur effizienten Lösung aller NP vollständigen
- Probleme verwendet werden können. Die Komplexitätstheorie befasst sich mit den Ressourcen, die zur Lösung von Problemen
- erforderlich sind und natürlich wurde sie zur Untersuchung des P vs NP Problems verwendet. Ein Ansatz ist der Versuch, untere Schranken für Schaltungen zu beweisen, d.h. Grenzen
- für die Größe von Schaltungen, die bestimmte Probleme lösen können. Obwohl auf diesem Gebiet Fortschritte zwar erzielt wurden, konnte das P vs NP Problem
- noch nicht damit gelöst werden. Reduktion und Vollständigkeitsbeweise sind mächtige Werkzeuge zur Untersuchung der Komplexität
- von Problemen. Eine Reduktion zeigt, dass ein Problem in ein anderes Problem transformiert werden kann
- und ein Vollständigkeitsbeweis zeigt, dass ein Problem wirklich NP vollständig ist, indem es eben auf ein bekanntes schweres NP vollständiges Problem reduziert wird.
- Viele Forscher haben diese Werkzeuge verwendet, um das P vs NP Problem zu untersuchen, aber bisher ist es niemandem gelungen zu beweisen, dass P eben nicht gleich NP ist.
- Schließlich haben sich die Forscher mit alternativen Rechenmodellen wie zum Beispiel Quantencomputing beschäftigt, um zu versuchen, P vs NP zu lösen.
- Die Quanteninformatik hat zwar gezeigt, dass sie bestimmte Probleme effizienter lösen kann als die klassische Informatik und damit echt mächtiger ist, aber es ist noch nicht
- klar, ob sie zur effizienten Lösung aller NP vollständigen Probleme eingesetzt werden kann.
- Es ist einfach noch nicht genügend Forschung. Das P vs NP Problem ist nach wie vor eines der wichtigsten offenen Probleme in der theoretischen
- Informatik und der Mathematik. Trotz jahrzehntelanger Forschung bleibt es tatsächlich ungelöst und es ist nicht ganz
- klar, ob es mit unserem derzeitigen System überhaupt wirklich gelöst werden kann. Eine der größten Herausforderungen bei der Erforschung des ganzen Problems ist der Mangel
- einfach an konkreten Beispielen für Probleme, die in NP sind, aber nicht in P sind. Die Suche nach neuen Beispielen für NP vollständige Probleme könnte dazu beitragen, dieses ganze
- Problem zu erleichtern und zu neuen Durchbrüchen führen. Aber trotz dieser Herausforderung wurden im Laufe der Jahre einige sehr bedeutende Fortschritte
- erzielt. Einer der wichtigsten Durchbrüche war die Entwicklung der Theorie der NP-Vollständigkeit
- durch Stephen Cook und Richard Karp in den 70ern. Diese Theorie zeigte, dass viele NP-Probleme eng miteinander verwandt sind und man sie
- einfach ineinander überführen kann, sodass sie alle gleich schwer zu lösen sind. Seitdem haben viele Forscher an der Entwicklung neuer Techniken und Ansätze zur Untersuchung
- von P vs NP gearbeitet und zu den jüngsten Entwicklungen gehört die Verwendung von algebraischer Geometrie und Optimierungstheorie zur Untersuchung des gesamten Problems.
- Das alles hat schon zu neuen Durchbrüchen geführt und jetzt können wir plötzlich sehr viele Probleme effizienter lösen als davor, aber das ganze Problem NP und P zu
- vergleichen, das haben wir noch immer nicht geschafft. Es ist also nach wie vor eine offene Frage, die in vielen Bereichen der aktiven Forschung
- weiter untersucht wird. Einer der wichtigsten Forschungsbereiche ist die Untersuchung der Komplexität von besagten
- Schaltkreisen und deren unteren Schranke. Die Forscher untersuchen auch die Verbindung zwischen diesen P vs NP Problemen und anderen
- wichtigen Fragen der Informatik und Mathematik, zum Beispiel die Frage, ob Quantencomputer NP-vollständige Probleme wirklich effizienter lösen können.
- Man geht aber aktuell zumindest davon aus, dass P nicht gleich NP ist. Und man geht sogar noch einen faszinierenden Schritt weiter.
- Man nimmt an, dass das Problem komplett unabhängig von den Standard-Aktionen der Mathematik ist. Was bedeutet, es könnte sogar unmöglich sein zu beweisen, dass P gleich oder ungleich NP
- ist. Zumindest mit unserem aktuellen mathematischen System.
- Allerdings ist auch das noch nicht bewiesen und auch daran wird noch gearbeitet. Und ja, auch wenn ihr es vermutlich nicht mehr hören könnt, durch die jüngsten Entwicklungen
- im Bereich KI kann hier auch nochmal ein ordentlicher Sprung möglich sein. KI wird genau in diesem Moment dazu genutzt, um riesige Datensätze zu analysieren.
- Beispielsweise eben die Datensätze der NP-vollständigen Probleme, um so vielleicht neue Muster oder Verbindungen zu offenbaren, die uns bislang einfach noch nicht aufgefallen sind.
- Auch zur Entwicklung von Algorithmen kann KI genutzt werden. Vielleicht kann hier ein Algorithmus gefunden werden, der ein Problem lösen kann, das bislang
- als unlösbar galt und vielleicht können wir dann eine Reduktion machen. Wer weiß das schon.
- Und auch für die Forschung rund um Quantenrechner kommt natürlich KI mittlerweile zum Einsatz. Aber das heißt natürlich nicht, dass jetzt plötzlich alles einfacher wurde.
- Denn P vs. NP und die gesamte Komplexitätstheorie bleibt genau das.
- Unfassbar komplex. Auch wenn der Name eigentlich nicht daherkommt.
- Wenn ihr mehr darüber lernen wollt, hier nochmal der Aufruf. Kommt gerne zu uns auf die Bootschrap Academy.
- Dort gibt es jede Menge Tutorials, auch in der theoretischen Informatik. Und ich freue mich natürlich immer, wenn begabte und schlaue Menschen ein Webinar beispielsweise
- geben wollen. Meldet euch gerne bei mir.
- Wir arbeiten auch gerade an einem neuen Feature, sodass ihr euch austauschen könnt. Also auch via Chat.
- Bislang ist der allerdings noch nicht fertig. Aber solange könnt ihr gerne schon mal unseren Discord-Server benutzen.
- Viel Spaß.