Education
17: Vorlesung| 0:00:00 Starten 0:00:53 Wiederholung Komplexitätstheorie 0:08:54 Polynominale Reduzierbarkeit 0:09:55 Beispiel 0:10:57 NP-harte und Np-Vollständige Probleme 0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ? 0:13:50 SAT: Das Erfüllbarkeitsproblem 0:17:03 Beweis von SAT 0:17:31 Beweis das SAT-NP-hart ist. 0:19:45 Variablen für F 0:24:53 Die Architektir von F= 0:27:08 Beweis w gehört zu der Sprache L, was daraus folgt das F erfüllbar ist 0:31:44 Es kann nur einen geben 0:33:05 Randbedingung 0:37:00 Anfangsbedingung 0:38:46 Übergangsbedingung Ü1, t->t+1 0:42:01 Übergangsbedingung Ü2, t->t+1 0:42:42 Endebedingung E 0:43:56 Gesamtgröße von F 0:48:06 Weitere NP-vollständige Probleme 0:55:04 3SAT (KNF) 0:56:56 Satz: 3SAT ist NP-vollständig 0:58:29 Beweis ""3SAT ist NP-hart"" 1:00:12 Negation in die Blätter drücken 1:01:23 Beispiel 1:03:04 Nichtblattknoten -> Neue Variablen 1:05:52 Beispiel 1:06:34 Erfüllbarkeitsäquivalenz von F1 1:07:57 Beispiel 1:10:15 F1 -> 3KNF