P vs. NP: Das MILLIONEN Dollar PROBLEM der Informatik
The Morpheus Tutorials
https://www.youtube.com/watch?v=4LUs6Q1q8xk

Transkript (automatisch erstellt)

0:00 Die Informatik ist ein Fachgebiet, das die Art und Weise, wie wir leben und arbeiten, revolutioniert hat.
0:06 Das stimmt immer wahrscheinlich alle zu. Von Smartphones über soziale Medien bis hin zu selbstfahrenden Autos.
0:11 Die Informatik hat die moderne Welt ziemlich entscheidend mitgeprägt. Und im Mittelpunkt steht immer wieder die Frage der Effizienz.
0:20 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?
0:29 Und daraus resultiert eine der ältesten und wichtigsten Fragen der Informatik. Das sogenannte P vs.
0:36 NP Problem. Bei diesem Problem geht es um die Frage, ob es möglich ist, Probleme effizient zu lösen,
0:44 die effizient verifiziert werden können oder nicht. Mit anderen Worten, wenn eine Lösung für ein Problem schnell und einfach überprüft
0:52 werden kann, gibt es dann einen Weg, diese Lösung ebenso schnell und einfach zu berechnen. Um das P vs.
0:59 NP Problem zu verstehen, müssen wir zunächst definieren, was wir eigentlich mit effizient meinen.
1:05 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
1:16 polynomiellen Funktion der Größe der Eingabe ist. Krass kompliziert formuliert, sage ich euch gleich, wie ich das meine.
1:24 Also beispielsweise ein Algorithmus, der eine Liste von n Zahlen in O von n hoch 2 Zeit sortieren kann, der gilt als polynomiell.
1:34 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.
1:44 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.
1:54 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.
2:05 Die Klasse der Probleme, die in polynomial Zeit gelöst werden können, wird als P oder die Klasse der einfachen Probleme bezeichnet.
2:15 Die Klasse der Probleme, die in polynomial Zeit verifiziert werden können, wird dagegen als NP oder als Klasse der harten Probleme bezeichnet.
2:24 Einige Beispiele für NP-Probleme sind das Travelling Salesman Problem, das Rucksack oder Knapsack Problem und das Buhl'sche Erfüllbarkeitsproblem.
2:33 Nehmen wir uns kurz nochmal das letzte. Als Beispiel schauen wir uns mal dieses NP-vollständige Problem, das Buhl'sche Erfüllbarkeitsproblem
2:42 genauer an, auch SAT-Problem übrigens genannt. Bei diesem Problem geht es um die Frage, ob es eine Menge von Buhl'schen Variablen, also
2:49 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
3:02 falsch ist und B und C wahr sind. Das SAT-Problem ist bekanntermaßen NP-vollständig.
3:10 Selbst wenn wir dieses Problem in Polynomialzeit lösen können, können wir jedes Problem in NP in Polynomialzeit lösen.
3:17 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,
3:27 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
3:39 werden. Wenn die Antwort auf diese Frage Ja lautet, dann wäre es möglich, viele schwierige Probleme,
3:45 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
3:55 zu lösen sind als andere und wir müssen uns nach neuen Problemlösungsmöglichkeiten umschauen.
4:02 Die Frage P vs. NP gilt als eines der Probleme, für deren Lösung es eine Million Dollar gibt.
4:09 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
4:17 euer Gehalt sich verzickfacht. Man geht derzeit davon aus, dass P nicht gleich NP ist.
4:24 Aber man weiß es nicht sicher. Man hat keinen Beweis dafür.
4:28 Eine Antwort hätte weitreichende Folgen, nicht nur für die Informatik. Das P vs.
4:34 NP Problem steht in engem Zusammenhang mit der Komplexitätstheorie, die sich mit den zur Lösung von Problemen erforderlichen Ressourcen befasst.
4:42 Wenn P nicht gleich NP ist, dann hat das Konsequenzen für viele andere Bereiche der Mathematik, einschließlich Algebra, Zahlentheorie und Kombinatorik.
4:53 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.
5:03 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
5:14 eben schwer zu lösen sind. Zum Beispiel eben die Faktorisierung großer Zahlen.
5:18 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
5:29 hier zugreift, angreifbar machen könnten. Wenn P allerdings nicht gleich NP ist, dann kann es möglich sein, kryptographische Protokolle
5:38 zu entwickeln, die wirklich gegen alle möglichen Angriffe bewiesen sicher sind. Das haben wir aktuell noch nicht.
5:44 In der Physik übrigens auch. Das P vs.
5:48 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.
5:58 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
6:09 und die Entdeckung von Medikamenten haben kann. Wenn P allerdings nicht gleich NP ist, kann es sein, dass die Simulation des Universums
6:17 Ressourcen oder Berechnungsmöglichkeiten erfordert, die die Möglichkeiten eines klassischen Computers wirklich übersteigen.
6:24 Eventuell also durch Quantencomputer vielleicht lösbar sind? Das P vs.
6:29 NP Problem wurde auch in anderen Bereichen untersucht, unter anderem in der Philosophie und den Wirtschaftswissenschaften.
6:35 In der Philosophie hängt das Problem mit der Frage zusammen, ob moralische Wahrheiten allein durch die Vernunft entdeckt werden können oder nicht.
6:46 Fragt mich bitte nicht wie, da bin ich ein bisschen raus. Wenn das jemand weiß, gerne in die Kommentare schreiben.
6:50 In den Wirtschaftswissenschaften bezieht sich das Problem auf die Frage, ob Märkte Ressourcen effizient zuweisen können oder nicht.
6:57 Okay, hier sind einige der wichtigsten Ansätze, die verwendet wurden, um solche Probleme anzugehen. Eine Möglichkeit, sich dem P vs.
7:08 NP Problem zu nähern, besteht darin, Brute-Force-Algorithmen zu verwenden, um NP vollständige Probleme zu lösen.
7:15 Diese Algorithmen probieren dann einfach alle Lösungen für ein Problem aus, bis sie eine korrekte Lösung gefunden haben.
7:24 Während der Ansatz für Kleininstanzen eines Problems funktionieren kann, wird er für Größeinstanzen einfach völlig unausführbar.
7:31 Die brauchen viel zu lang. Brute-Force-Algorithmen sind zwar in der Lage, diese NP vollständigen Probleme zu lösen,
7:39 aber eben wahnsinnig ineffizient. Am Beispiel unseres SAT-Problems von vorhin.
7:43 Ich muss alle Möglichkeiten, also alle Variablenbelegungen, komplett ausprobieren, um herauszufinden, ob sie die Gleichung lösen oder nicht.
7:52 Ein anderer Ansatz besteht darin, Algorithmen zu entwickeln, die NP vollständige Probleme in polynomialer Zeit lösen können.
8:00 Oder eben effiziente Datenstrukturen zu entwickeln, die das Lösen dieser Probleme überhaupt erst ermöglichen.
8:05 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.
8:15 Und manche saßen da wirklich Jahrzehnte dran. Ein dritter Ansatz besteht darin, probabilistische Algorithmen oder randomisierte Algorithmen
8:25 zur Lösung NP vollständiger Probleme zu finden. Diese Algorithmen machen sich den Zufall zunutze, um Berechnungen zu beschleunigen und haben
8:33 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
8:44 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
8:54 Probleme verwendet werden können. Die Komplexitätstheorie befasst sich mit den Ressourcen, die zur Lösung von Problemen
9:02 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
9:13 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
9:23 noch nicht damit gelöst werden. Reduktion und Vollständigkeitsbeweise sind mächtige Werkzeuge zur Untersuchung der Komplexität
9:30 von Problemen. Eine Reduktion zeigt, dass ein Problem in ein anderes Problem transformiert werden kann
9:37 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.
9:49 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.
10:00 Schließlich haben sich die Forscher mit alternativen Rechenmodellen wie zum Beispiel Quantencomputing beschäftigt, um zu versuchen, P vs NP zu lösen.
10:12 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
10:22 klar, ob sie zur effizienten Lösung aller NP vollständigen Probleme eingesetzt werden kann.
10:28 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
10:36 Informatik und der Mathematik. Trotz jahrzehntelanger Forschung bleibt es tatsächlich ungelöst und es ist nicht ganz
10:43 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
10:53 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
11:07 Problem zu erleichtern und zu neuen Durchbrüchen führen. Aber trotz dieser Herausforderung wurden im Laufe der Jahre einige sehr bedeutende Fortschritte
11:16 erzielt. Einer der wichtigsten Durchbrüche war die Entwicklung der Theorie der NP-Vollständigkeit
11:23 durch Stephen Cook und Richard Karp in den 70ern. Diese Theorie zeigte, dass viele NP-Probleme eng miteinander verwandt sind und man sie
11:32 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
11:43 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.
11:52 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
12:03 vergleichen, das haben wir noch immer nicht geschafft. Es ist also nach wie vor eine offene Frage, die in vielen Bereichen der aktiven Forschung
12:10 weiter untersucht wird. Einer der wichtigsten Forschungsbereiche ist die Untersuchung der Komplexität von besagten
12:17 Schaltkreisen und deren unteren Schranke. Die Forscher untersuchen auch die Verbindung zwischen diesen P vs NP Problemen und anderen
12:24 wichtigen Fragen der Informatik und Mathematik, zum Beispiel die Frage, ob Quantencomputer NP-vollständige Probleme wirklich effizienter lösen können.
12:32 Man geht aber aktuell zumindest davon aus, dass P nicht gleich NP ist. Und man geht sogar noch einen faszinierenden Schritt weiter.
12:41 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
12:55 ist. Zumindest mit unserem aktuellen mathematischen System.
12:57 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
13:08 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.
13:18 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.
13:26 Auch zur Entwicklung von Algorithmen kann KI genutzt werden. Vielleicht kann hier ein Algorithmus gefunden werden, der ein Problem lösen kann, das bislang
13:35 als unlösbar galt und vielleicht können wir dann eine Reduktion machen. Wer weiß das schon.
13:39 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.
13:48 Denn P vs. NP und die gesamte Komplexitätstheorie bleibt genau das.
13:54 Unfassbar komplex. Auch wenn der Name eigentlich nicht daherkommt.
13:57 Wenn ihr mehr darüber lernen wollt, hier nochmal der Aufruf. Kommt gerne zu uns auf die Bootschrap Academy.
14:02 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
14:10 geben wollen. Meldet euch gerne bei mir.
14:12 Wir arbeiten auch gerade an einem neuen Feature, sodass ihr euch austauschen könnt. Also auch via Chat.
14:19 Bislang ist der allerdings noch nicht fertig. Aber solange könnt ihr gerne schon mal unseren Discord-Server benutzen.
14:24 Viel Spaß.