Education
09 | 0:00:00 Starten 0:00:39 NP-Vollständigkeit 0:02:03 Transitivität der poly. Transformation 0:02:31 Korollar 0:03:49 Das Problem 3-SAT 0:05:37 Beweis: NP-Vollständigkeit von 3-SAT 0:20:16 Das Problem 2SAT 0:22:09 Das Problem MAX2SAT 0:24:18 Das Problem CLIQUE 0:27:48 Beweis: NP-Vollständigkeit von CLIQUE 0:36:44 Das Problem COLOR 0:37:57 Beweis: NP-Vollständigkeit von 3COLOR 0:39:06 Konstruktion von 3COLOR-Instanz G 0:43:16 Beispielgraph zur Reduktion 0:45:12 Polynomialität der Reduktion 0:45:35 Instantz I erfüllbar auch Instanz G erfüllbar 0:45:57 Instanz G ist 3-färbbar 0:50:30 Das Problem EXACT COVER 0:53:51 Beweis: NP-Vollständigkeit von EXACT COVER 0:55:30 Konstruktion von (X,S) 1:04:50 G dreifärbbar (X,S) hat exakte Überdeckung