Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Das P-NP-Problem: Wo sind die Grenzen dessen, was Computer berechnen können?
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 20 Zeilen
- 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
- 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
- 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
- Konstante die Laufzeit nur ist. Und die Praxiserfahrung ist, dass polynomielle Laufzeiten n², n hoch 3 und sowas n hoch irgendeine Konstante, dass die
- 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
- 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
- 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
- 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
- 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,
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- exponentiell oder es geht eben nicht polynomiell. Und deswegen ist noch so diese Restfunken Hoffnung davon, vielleicht komme ich hier auf den
- polynomiellen Algorithmus und da gibt's schon das eine oder andere Management, was dann sagt hier lieber Softwareenieur, lös doch mal dieses
- Problem etwas schneller und bisher können dann die Softwareenieure nur sagen, das stößt an die Grenzen der theoretischen Informatik und nicht, das
- ist bewiesenermaßen unmöglich dieses Problem schnell zu lösen. Das ist so grob formuliert das PNP Problem. M.
Zum Nachlesen
DorFuchs2013: Fast Forward Science, Spezialpreis der Jury, für seinen Song zur Mitternachtsformel (a-b-c-Formel). Beurich erhielt ein Preisgeld in Höhe von 2000 …
MathematikAn deutschen Universitäten gehört die Mathematik meistens zur selben Fakultät wie die Naturwissenschaften, und so wird Mathematikern nach der Promotion in der …