Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 06.12.2016, 09 - a podcast by Karlsruher Institut für Technologie (KIT)

09 |
0:00:00 Starten
0:06:41 Das Problem SUBSET SUM
0:07:46 NP-Vollständigkeit von SUBSET SUM
0:24:03 Das Problem PARTITION
0:31:06 Das Problem KNAPSACK
0:37:32 Auswirkungen auf die Frage P=NP
0:45:42 Zusammenfassung
0:47:57 Die Klassen NPI, co-P und co-NP
0:54:22 Das TSP-Komplement-Problem
0:57:40 Lemma
1:00:00 Bemerkung
1:01:25 Das Problem Subgraphisomorphie
1:03:14 Das Problem Graphismorphie
1:09:06 Suchprobleme
1:10:21 Beispiel: TSP-Suchproblem
1:11:03 Beispiel: Hamilton–Kreis Suchproblem
1:12:04 Aufzählungsprobleme
1:12:44 Reduzierbarkeit für Suchprobleme
1:15:36 Orakel-Turing-Machine
1:19:40 NP-schwer
1:20:39 Beweisskizze

Further episodes of Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

Further podcasts by Karlsruher Institut für Technologie (KIT)

Website of Karlsruher Institut für Technologie (KIT)