Die wichtigste offene Frage der Theoretischen Informatik: NP-vollständige Probleme

Als Abschluss des Rundflugs über die Komplexitätstheorie der Satz von Cook und Levin, der die Existenz eines NP-vollständigen Problems (SAT, Erfüllbarkeitsproblem der Aussagenlogik) demonstriert. Das führt zur P-NP-Frage, die eines der sieben Millennium-Probleme ist. Im Anschluss wird gezeigt, wie man darauf aufbauend zu weiteren Problemen dieser Art kommt. Außerdem eine Charakterisierung von NP als Klasse der Probleme, deren Lösungen man "schnell überprüfen" (in Polynomialzeit verifizieren) kann.
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/ti-skript.pdf
* Ausführliche Playlist zur Komplexitätstheorie (Sommersemester 2014): • Theoretische Informati...
* Mehr zur Zeitin-Transformation: • Beweise färben - Überz...
* Das Video im Playlist-Kontext: weitz.de/y/irCAnmXfsFw?list=PL...
* Liste aller Videos: weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* "FAQ": weitz.de/youtube.html
00:00 In Polynomialzeit verifizierbare Probleme
02:34 Erfüllbarkeitsproblem der Aussagenlogik
07:36 Charakterisierung von NP durch Zertifikate
11:46 NP-vollständige Probleme
15:17 Der Satz von Cook und Levin
31:37 CNF-SAT ist auch NP-vollständig
38:09 CLIQUE ist NP-vollständig
44:59 Das P-NP-Problem
47:26 Typische Missverständnisse
54:20 Umgang mit NP-vollständigen Problemen