Komplexitätstheorie

Vorlesung: Montags 09:00-10:30 im Raum C112
Dozent: Jens M. Schmidt
Übung: Donnerstags 13:00-14:30 im Raum C112 (ungerade Wochen)
Tutor: Jens M. Schmidt
SWS: 2V+1Ü
Zielgruppe: 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. Am Ende des Semesters 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.


Datum Inhalt Übung
04.04.2016 Berechenbarkeit Sprachen, Entscheidungsprobleme, Eingabe- und Ausgabespezifikation algorithmischer Probleme, Abzählbarkeitsargument
11.04.2016 Berechenbarkeit Berechnungsmodelle, RAM und Kostenmaße, Turingmaschine, (Semi-)Entscheidbarkeit, partielle und totale Berechenbarkeit ueb01.pdf
18.04.2016 Berechenbarkeit Worst-Case-Laufzeit, Zeitkomplexität, O-Notation, Church-Turing-These, Simulationen zwischen TM und RAM
25.04.2016 Berechenbarkeit Universelle TMs, Unentscheidbare Probleme, Diagonalsprache, Komplement, Halteproblem, Reduktionen ueb02.pdf
02.05.2016 Berechenbarkeit
Satz von Rice, Postsches Korrespondenzproblem
09.05.2016 Zeitkomplexität Untere Schranken mit Kreuzungsfolgen, DTIME, Zeitkonstruierbare Funktionen ueb03.pdf
16.05.2016 Pfingsten
23.05.2016 Zeitkomplexität Zeithierarchiesatz, P, EXP Bonus.pdf
30.05.2016 NP-Vollständigkeit Turingreduktionen, Optimierungs- und Entscheidungsvarianten wichtiger Probleme, NP, NTMs
06.06.2016 NP-Vollständigkeit Alternative NP-Charakterisierung, Polynomialzeitreduktionen, SAT auf 3-SAT, 3-SAT auf DHC ueb05.pdf
13.06.2016 NP-Vollständigkeit NP-Vollständigkeit, Satz von Cook
20.06.2016 Diagonalisierung Starke NP-Vollständigkeit, NP-Intermediate, Satz von Ladner ueb06.pdf
04.07.2016 Diagonalisierung Orakelklassen, Grenzen der Diagonalisierung
11.07.2016 Diagonalisierung Satz von Baker-Gill-Solovay, co-NP und Beziehung zu NP ueb07.pdf
14.07.2016 Polynomielle Hierarchie Polynomielle Hierarchie, Quantorencharakterisierung, Zusammenfall