10 | 0:00:00 Start 0:00:27 Letzte/Diese Vorlesung 0:04:04 Das Problem SUBSET SUM 0:05:37 NP-Vollständigkeit von SUBSET SUM 0:21:39 Das Problem PARTITION 0:22:29 Beweis: NP-Vollständigkeit von PARTITION 0:28:40 Das Problem KNAPSACK 0:31:18 Beweis: NP-Vollständigkeit von KNAPSACK 0:33:39 Auswirkung auf die Frage P= NP 0:40:15 Zusammenfassung 0:45:01 Die Klassen NPC und NPI 0:46:23 Die Klassen co-P und co-NP 0:51:28 Das TSP-Komplement-Problem 0:54:27 NP-vollständig vs. co-NP 0:58:19 Das Problem Subgraphisomorphie 1:00:17 Das Problem Graphisomorphie 1:02:06 Die Polynomielle Hierarchie 1:12:34 Suchprobleme 1:13:13 Beispiel: TSP-Suchproblem 1:14:53 Beispiel: Hamilton-Kreis Suchproblem 1:16:18 NP-Schwere bei Suchproblemen 1:20:15 Beispiel: Hamilton-Kreis Aufzählungsproblem