Komplexitätstheorie (Sommer 2018)

Vorlesung: Dienstags 11:00-12:30 im Raum C112/113
Dozent: Jens M. Schmidt
Übung: Donnerstags 09:00-10:30 im Raum C112 (ungerade Wochen)
Tutor: Solomon Lo
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 eigener Lösungen von Ü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. (11.4. 13:00 C112) 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.
Maifeiertag
06. Berechenbarkeit
Satz von Rice, Postsches Korrespondenzproblem ueb03.pdf
07. Zeitkomplexität Untere Schranken mit Kreuzungsfolgen, DTIME
08. Zeitkomplexität Zeitkonstruierbare Funktionen, Zeithierarchiesatz, P, EXP ueb04.pdf
09. NP-Vollständigkeit Turingreduktionen, Optimierungs- und Entscheidungsvarianten wichtiger Probleme, NP, NTMs
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