Education
08 | 0:00:00 Starten 0:00:37 Wiederholung: NP-Vollständigkeit 0:06:10 Wiederholung: Transitivität der poly. Transformation 0:06:40 Wiederholung: Korollar 0:07:37 Wiederholung: Das Problem SAT (satisfiability) 0:12:17 Das Problem 3-SAT 0:13:13 Beweis: NP-Vollständigkeit von 3-SAT 0:30:07 Das Problem 2SAT 0:34:40 Das Problem MAX2SAT 0:38:02 Das Problem CLIQUE 0:39:32 Beweis: NP-Vollständigkeit von CLIQUE 0:51:19 Das Problem COLOR 0:54:56 Beweis: NP-Vollständigkeit von 3COLOR 0:57:29 Konstruktion von 3COLOR-Instanz G 1:01:05 Beispielgraph zur Reduktion 1:04:20 Polynomialität der Reduktion 1:04:56 Instanz I erfüllbar => Instanz G erfüllbar 1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar 1:08:02 Das Problem EXACT COVER 1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER 1:14:28 Konstruktion von (X,S) 1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung 1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung