Das P-NP-Problem: Wo sind die Grenzen dessen, was Computer berechnen können?
DorFuchs
https://www.youtube.com/watch?v=QgtkircWtYU

Transkript (automatisch erstellt)

0:00 Das PNP Problem ist das wichtigste ungelöste Problem in der theoretischen Informatik und ist auch eines der Millennium Probleme, für dessen Lösung
0:09 es eine Million Dollar Preisgeld gibt. Die Frage ist, ob es für jedes Problem, wo der Computer schnell die Lösung, wenn sie da ist, überprüfen kann, dass ihr
0:16 richtig ist, auch ein Algorithmus gibt, der die Lösung schnell finden kann. Und schnell bedeutet jetzt hier polynomielle Laufzeit. Das sozusagen n hoch eine
0:26 Konstante die Laufzeit nur ist. Und die Praxiserfahrung ist, dass polynomielle Laufzeiten n², n hoch 3 und sowas n hoch irgendeine Konstante, dass die
0:35 beherrschbar sind und gut skaleren. Auch wenn das n groß wird, kriegt man das noch Entengriff. Ganz im Gegensatz zu sowas wie exponentiellen Wachstum 2 hoch
0:42 n oder 10 hoch n oder 1000 hoch n, das eskaliert ja so schnell, wenn mein n hier auch nur ein kleines bisschen weiter wächst, dann wird das immer um
0:49 den Faktor A multipliziert und wird immer komplexer und solche Probleme kriegt man kaum in den Griff. Stell dir z.B. bevor du machst Sudoku nicht nur
0:57 mit so kleinen 3 x 3 quadrat die ein großes 3 x 3 Quadrat bilden, sondern mit n Quadraten, die ein großes Nrid bilden. Und bei Sudoku ist es natürlich recht
1:06 leicht, wenn Sudoku fertig gelöst ist, noch mal zu kontrollieren, ob wirklich alles stimmt. Das ist dann polynomielle Laufzeit. Ich kriege das fertige Sudoku,
1:14 check da einmal drüber, das geht schnell. Aber das Sodoku selbst zu lösen, Lösungsalgorithmus dafür, das ist schwierig. Da sind bisher nur
1:24 exponentielle Laufzeiten bekannt, die Sudoku komplett lösen können als Algorithmus. Also P sind alle Probleme, wo man die Lösung in polynomieller Zeit
1:33 schnell finden kann und n sind die Probleme, wo man mit polynomieller Zeit die Lösung überprüfen kann, wenn schon eine da ist. Und die Frage ist halt, ob
1:41 ich die auch in polynomieller Zeit finden kann, also ob P = NP ist und diese Probleme gleich sind. Und man kennt jetzt ganz viele Probleme, die np
1:49 vollständig sind. Also, wo man weiß, wenn ich dieses eine Problem in polynomialer Zeit lösen kann, dann kann ich alle Probleme in NP in polynomieller
1:57 Zeit lösen. Und das ist halt das Spannende. Es gibt viele Probleme, wo man das Gefühl hat, vielleicht gibt's hier einen cleveren Algorithmus und ich
2:04 komme nur nicht drauf. Und das sind dann oftmals Stellen, wo man auf das PNP Problem stößt, wo noch keiner beweisen konnte, nee, es geht nicht schneller als
2:12 exponentiell oder es geht eben nicht polynomiell. Und deswegen ist noch so diese Restfunken Hoffnung davon, vielleicht komme ich hier auf den
2:19 polynomiellen Algorithmus und da gibt's schon das eine oder andere Management, was dann sagt hier lieber Softwareenieur, lös doch mal dieses
2:25 Problem etwas schneller und bisher können dann die Softwareenieure nur sagen, das stößt an die Grenzen der theoretischen Informatik und nicht, das
2:32 ist bewiesenermaßen unmöglich dieses Problem schnell zu lösen. Das ist so grob formuliert das PNP Problem. M.