Education
10 | 0:00:00 Starten 0:03:27 Das Problem SUBSET SUM 0:04:50 NP-Vollständigkeit von SUBSET SUM 0:18:59 Das Problem Partition 0:25:38 Das Problem KNAPSACK 0:28:21 Beweis: NP-Vollständigkeit von KNAPSACK 0:32:43 Auswirkung auf die Frage P=NP 0:37:29 Zusammenfassung 0:41:47 Die Klassen NPI, co-P und co-NP 0:45:07 Vermutete Situation 0:50:03 Das TSP-Komplement-Problem 0:52:03 Lemma 1:02:23 Suchprobleme 1:05:08 Beispiel: TSP-Suchproblem 1:06:53 Beispiel: Hamilton-Kreis Suchproblem 1:08:09 Aufzählungsprobleme 1:09:11 Reduzierbarkeit für Suchprobleme 1:12:28 Orakel-Turing-Maschine 1:13:56 Orakel-TM: Verhalten im Fragezustand 1:16:35 Turing-Reduktion 1:19:07 NP-schwer 1:22:30 Beweisskizze