KIT | KIT-Bibliothek | Impressum | Datenschutz

07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 22.11.2018

Ueckerdt, Torsten; KIT | Webcast [Hrsg.]

  • 0:00:00 Start
  • 0:00:03 NP-Vollständigkeit für Sprachen
  • 0:03:38 NP-Vollständigkeit für Entscheidungsprobleme
  • 0:05:28 Transitivität der poly. Transformation
  • 0:06:59 Beobachtung
  • 0:10:58 Das Problem SAT (satisfiability)
  • 0:16:04 Weitere Beispiele für SAT-Instanzen
  • 0:17:42 Der Satz von Cook (Steven Cook, 1971)
  • 0:22:03 Beweis: das Setup
  • 0:28:37 Beweis: Konstruktion der Variablen
  • 0:32:52 Beweis: Zielsetzung
  • 0:37:44 Beweis: Konstruktion der Klauseln
  • 0:38:03 Klauselgruppe 1:
  • 0:39:46 Klauselgruppe 2:
  • 0:40:36 Klauselgruppe 3:
  • 0:41:32 Klauselgruppe 4:
  • 0:44:44 Klauselgruppe 5:
  • 0:45:27 Klauselgruppe 6:
  • 0:47:04 Klauselgruppe 6,1:
  • 0:48:59 Klauselgruppe 6,2:
  • 0:52:30 Zwischenbilanz
  • 0:58:13 Polynomialität der Transformation
  • 0:58:34 Polynomialität - Klauselgruppe 1:
  • 0:59:31 Polynomialität - Klauselgruppe 2:
  • 1:00:12 Polynomialität - Klauselgruppe 3:
  • 1:00:45 Polynomialität - Klauselgruppe 4:
  • 1:01:31 Polynomialität - Klauselgruppe 5:
  • 1:01:44 Polynomialität - Klauselgruppe 6,1:
  • 1:02:15 Polynomialität - Klauselgruppe 6,2:
  • 1:04:09 Heute im Rückblick: Der Satz von Cook


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 23.11.2018
Erstellungsdatum 22.11.2018
DOI 10.5445/DIVA/2018-880
Identifikator KITopen-ID: 1000116064
Serie Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page