Komplexitätstheorie (Sommer 2019)

Vorlesung: Donnerstags 09:00-10:30 im Raum C112
Dozent: Jens M. Schmidt
Übung: Donnerstags 11:00-12:30 im Raum C110 (gerade Wochen)
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 Vorlesungszeit wird eine mündliche Prüfung angeboten.
Skript:
wird am Anfang der Vorlesung ausgegeben
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 Übung
01 Berechenbarkeit Sprachen, Entscheidungsprobleme, Eingabe- und Ausgabespezifikation algorithmischer Probleme, Abzählbarkeitsargument
02 Berechenbarkeit Berechnungsmodelle, RAM und Kostenmaße, Turingmaschine, (Semi-)Entscheidbarkeit, partielle und totale Berechenbarkeit ueb01.pdf
03 Berechenbarkeit Worst-Case-Laufzeit, Zeitkomplexität, O-Notation, Church-Turing-These, Simulationen zwischen TM und RAM
04 Berechenbarkeit Universelle TMs, Unentscheidbare Probleme, Diagonalsprache, Komplement, Halteproblem, Reduktionen ueb02.pdf
05 Berechenbarkeit
Satz von Rice, Postsches Korrespondenzproblem
06 ZeitkomplexitätUntere Schranken mit Kreuzungsfolgen, DTIMEueb03.pdf
07 ZeitkomplexitätZeitkonstruierbare Funktionen, Zeithierarchiesatz, P, EXP
08 NP-VollständigkeitTuringreduktionen, Optimierungs- und Entscheidungsvarianten wichtiger Probleme, NP, NTMsueb04.pdf
09
Christi Himmelfahrt

10 NP-Vollständigkeit Alternative NP-Charakterisierung, Polynomialzeitreduktionen, SAT auf 3-SAT, 3-SAT auf DHC ueb05.pdf
11 NP-Vollständigkeit NP-Vollständigkeit, Satz von Cook
12 Diagonalisierung Starke NP-Vollständigkeit, NP-Intermediate, Satz von Ladner 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