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

Autor

Torsten Ueckerdt

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

07 |
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

Laufzeit (hh:mm:ss)

01:08:33

Serie

Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19

Publiziert am

23.11.2018

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz