Education
09 | 0:00:00 Start 0:00:08 Letzte Vorlesung 0:08:16 Plan für heute 0:10:46 Das Problem 3SAT 0:12:53 Beweis: NP-Vollständigkeit von 3SAT 0:31:50 Das Problem 2SAT 0:34:00 Das Problem MAX2SAT 0:36:49 Das Problem CLIQUE 0:39:07 Beweis: NP-Voillständigkeit von CLIQUE 0:54:25 Das Problem COLOR 0:55:33 Beweis: NP-Vollständigkeit von 3COLOR 0:57:09 Konstruktion von 3COLOR-Instanz G 1:02:30 Polynomialität der Reduktion 1:03:12 Instanz G 3-färbbar 1:08:08 Zwischenstand Polynomiale Reduktion 1:10:27 Das Problem EXACT COVER 1:12:53 Beweis: NP-Vollständigkeit von EXACT COVER 1:14:34 Konstruktion von (X, S) 1:22:00 G 3-färbbar -> exakte Überdeckung