Education
18: Vorlesung und Übung| 0:00:00 Starten 0:00:10 Wiederholung: Satz: 3SAT ist NP-vollständig 0:02:06 Wiederholung: Beweis ""3SAT ist NP-hart"" 0:02:47 Wiederholung: Negationen in die Blätter drücken 0:03:07 Wiederholung: Nichtblattknoten --> Neue Variablen 0:03:37 Wiederholung: Erfüllbarkeitsäquivalenz 0:05:05 Exkurs: 2SAT ∈ P 0:10:27 CLIQUE 0:14:22 Beweis Clique ∈ NP 0:15:01 Beweis von ""CLIQUE ist NP-hart"" 0:19:57 Beispiel 0:29:19 VERTEX COVER (Knotenüberdeckung) 0:31:14 Beweis VERTEX COVER ∈ NP 0:31:32 Beweis von ""VERTEX COVER ist NP-hart"" 0:39:11 Gesehene Reduktionen 0:39:39 Beweistechniken für A ≤p B: Spezialfälle 0:43:36 Beweistechniken für A ≤p B: Uminterpretation 0:44:28 Beweistechniken für A ≤p B: Gadgets 0:46:27 Beweistechniken für A ≤p B: Randbedingungen 0:47:33 9. Übung 0:47:35 Komplexitätsklassen - Einführung 0:56:38 Komplexitätsklassen - Fortführung 1:03:57 3SAT ≤p 3COLOR - Einführung 1:05:16 3SAT ≤p 3COLOR - Fortführung 1:09:00 3SAT ≤p 3COLOR - mit Gadget 1:14:08 1-aus-3SAT 1:20:37 XOR-(3)SAT 1:23:07 Einige weitere Varianten 1:26:08 PLANAR 3SAT 1:28:05 Knapsack und Subset Sum