KIT | KIT-Bibliothek | Impressum | Datenschutz

10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 05.12.2017

Wagner, Dorothea; KIT | Webcast [Hrsg.]

  • 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
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 07.12.2017
Erstellungsdatum 05.12.2017
DOI 10.5445/DIVA/2017-752
Identifikator KITopen-ID: 1000115135
Lizenz KITopen-Lizenz
Serie Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18
Folge 10
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page