08: NP-Vollständigkeit in der Komplexitätstheorie: 3SAT, 2SAT, MAX2SAT, CLIQUE & 3COLOR 🎯

0:00:00 Start
0:00:22 Letzte Vorlesung
0:06:59 Plan für heute
0:09:46 Das Problem 3SAT
0:11:29 Beweis: NP-Vollständigkeit von 3SAT
0:30:58 Das Problem 2SAT
0:31:54 Das Problem MAX2SAT
0:33:51 Das Problem CLIQUE
0:35:32 Beweis: NP - Vollständigkeit von CLIQUE
0:48:25 Das Problem COLOR
0:50:25 NP-Vollständigkeit von 3COLOR
0:52:26 Konstruktion von 3COLOR-Instanz G
0:55:48 Polynomialität der Reduktion
0:56:35 Instanz/ erfüllbar
1:03:01 Zwischenstand Polynomiale Reduktion
1:13:41 Das Problem EXACT COVER
1:16:23 NP - Vollständigkeit von EXACT COVER
1:18:00 Konstruktion

Dozent:
Torsten Ueckerdt | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik

Vorlesungsaufzeichnung: KIT | WEBCAST
http://webcast.kit.edu