10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 05.12.2017 - a podcast by Karlsruher Institut für Technologie (KIT)

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

Further episodes of Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

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

Website of Karlsruher Institut für Technologie (KIT)