Komplexitätstheorie (Sommer 2020)

Vorlesung: wird mit Vorlesungsvideos und Besprechungen online gehalten. Die erste Besprechung findet am 21.04.2020 um 15:00 Uhr statt. Bitte beim Dozenten per email anmelden.
Dozent: Jens M. Schmidt
Übung: wird online 2-wöchig ab 04.05.2020 als Webinar gehalten. Die Lösungen bitte so vorbereiten, dass Sie online vorgestellt werden können.
Tutor: Jens M. Schmidt
SWS: 2V+1Ü
Zielgruppe: Mathematik Bachelor 6. Fachsemester, Mathematik Master 2. Fachsemester
Voraussetzungen: Einführung in die Diskrete Mathematik, Graphen und Algorithmen
Prüfung:
Prüfungsvoraussetzungen sind die regelmäßige und aktive Mitarbeit in den Übungen und das Vorstellen von eigenen Lösungen der Übungsaufgaben. Zum Ende der Vorlesung wird eine mündliche Prüfung angeboten.
Skript:
Ein vorläufiges Skript ist hier verfügbar.
Literatur:



I. Wegener - Komplexitätstheorie: Grenzen der Effizienz von Algorithmen, 2003.
S. Arora, B. Barak - Computational Complexity: A Modern Approach, 2009.
M. Sipser - Introduction to the Theory of Computation, 3rd edition, 2012.
R. Reischuk - Komplexitätstheorie, Band I: Grundlagen, 2. Auflage, 1999.


Nr.
Inhalt Vorlesungs-
Videos + Notes

Übung
01 Berechenbarkeit Sprachen, Entscheidungsprobleme, Eingabe- und Ausgabespezifikation algorithmischer Probleme, Abzählbarkeitsargument 01.mkv + 01.pdf
02.mkv + 02.pdf

02 Berechenbarkeit Berechnungsmodelle, RAM und Kostenmaße, Turingmaschine, (Semi-)Entscheidbarkeit, partielle und totale Berechenbarkeit 03.mkv + 03.pdf
04.mkv + 04.pdf
ueb01.pdf
03 Berechenbarkeit Worst-Case-Laufzeit, Zeitkomplexität, O-Notation, Church-Turing-These, Simulationen zwischen TM und RAM 05.mkv + 05.pdf
06.mkv + 06.pdf

04 Berechenbarkeit Universelle TMs, Unentscheidbare Probleme, Diagonalsprache, Komplement, Halteproblem, Reduktionen 07.mkv + 07.pdf
08.mkv + 08.pdf
ueb02.pdf
05 Berechenbarkeit
Satz von Rice, Postsches Korrespondenzproblem09.mkv + 09.pdf
10.mkv + 10.pdf

06 ZeitkomplexitätUntere Schranken mit Kreuzungsfolgen, DTIME11.mkv + 11.pdf
12.mkv + 12.pdf
ueb03.pdf
07 ZeitkomplexitätZeitkonstruierbare Funktionen, Zeithierarchiesatz
13.mkv + 13.pdf
14.mkv + 14.pdf

08 NP-VollständigkeitP, EXP, Turingreduktionen, Optimierungs- und Entscheidungsvarianten wichtiger Probleme15.mkv + 15.pdf ueb04.pdf
09 NP-Vollständigkeit NP, NTMs, Alternative NP-Charakterisierung 16.mkv + 16.pdf
17.mkv + 17.pdf

10 NP-Vollständigkeit Polynomialzeitreduktionen, SAT auf 3-SAT, 3-SAT auf DHC 18.mkv + 18.pdf
19.mkv + 19.pdf
ueb05.pdf
11 NP-Vollständigkeit NP-Vollständigkeit, Satz von Cook 20a.mkv+20.pdf
20b.mkv

12 Diagonalisierung Starke NP-Vollständigkeit, NP-Intermediate, Satz von Ladner 21.mkv + 21.pdf
22.mkv + 22.pdf
ueb06.pdf
13 Diagonalisierung Orakelklassen, Grenzen der Diagonalisierung

14 Diagonalisierung Satz von Baker-Gill-Solovay, co-NP und Beziehung zu NP
ueb07.pdf
15 Polynomielle Hierarchie Polynomielle Hierarchie, Quantorencharakterisierung, Zusammenfall