Die wichtigste offene Frage der Theoretischen Informatik: NP-vollständige Probleme скачать в хорошем качестве

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: http://weitz.de/GDM/ Das NEUE Buch: http://weitz.de/PP/ Skript: http://weitz.de/files/ti-skript.pdf Ausführliche Playlist zur Komplexitätstheorie (Sommersemester 2014):    • Theoretische Informatik (Sommersemester 2014)   Mehr zur Zeitin-Transformation:    • Beweise färben - Überzeugen, ohne etwas zu...   Das Video im Playlist-Kontext: http://weitz.de/y/irCAnmXfsFw?list=PL... Liste aller Videos: http://weitz.de/haw-videos/ Das etwas andere Mathe-Lehrbuch: http://weitz.de/KMFI/ "FAQ": http://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