Komplexitätstheorie (Sommersemester 2016)

Vorlesung: Prof. Dr. Markus Müller-Olm

Übungen: Prof. Dr. Markus Müller-Olm, Sebastian Kenter

Eintrag für diese Veranstaltung im HIS/LSF

Hinweise

  • Wie in der letzten Übung am 13.07. besprochen, wird es am Freitag, dem 22.07., um 14:15 Uhr, einen zusätzlichen Termin geben, in dem weitere inhaltliche Fragen besprochen werden können. Treffpunkt ist der Flur des 7. Stockwerks; anschließend suchen wir zusammen einen freien Raum.

Ort und Zeit

  • Vorlesung: Mo 10:15-11:45 Uhr, M2 und Do 10:15-11:45 Uhr, M2.
  • Übungen: Mi, 10:15-11:45 Uhr, M6 oder M2.

Vorlesungsinhalt

Die Komplexitätstheorie ist ein zentrales Gebiet der (theoretischen) Informatik. Sie beschäftigt sich mit der Frage, welche Mindestresourcen zur Lösung algorithmischer Probleme benötigt werden. Mit der Frage, ob die Klassen P und NP tatächlich, wie von nahezu allen Experten vermutet, verschieden sind, hat die Komplexitätstheorie ein sehr prominentes, auch Nichtexperten bekanntes offenes Problem. Die Vorlesung soll zum einen eine Einführung in klassische Techniken und Resultate der Komplexitätstheorie geben und behandelt deshalb Themen wie:

  • Das Berechnungsmodell und die Klasse P
  • NP und NP-Vollständigkeit
  • Hierarchiesätze und Diagonalisierung
  • Platzkomplexitätsklassen
  • Die polynomielle Hierarchie und Alternierung
  • Randomisierte Komplexitätsklassen

Je nach der zur Verfügung stehenden Zeit soll darüber hinaus eine Auswahl weiterführender Themen behandelt werden, wie z.B.:

  • Nichtuniforme Komplexität und Schaltkreiskomplexität
  • Kommunikationskomplexität
  • Interaktive Beweise
  • Quantenkomplexität
  • PCP-Theorem

 

Übungen

Die erste Übung findet am Mittwoch, dem 27.04.16 statt.

Übungsblätter

  • Blatt 1, 21.04.2016 [pdf]
  • Blatt 2, 28.04.2016 [pdf]
  • Blatt 3, 04.05.2016 [pdf]
  • Blatt 4, 12.05.2016 [pdf]
  • Blatt 5, 25.05.2016 [pdf]
  • Blatt 6, 02.06.2016 [pdf]
  • Blatt 7, 09.06.2016 [pdf]
  • Blatt 8, 16.06.2016 [pdf]
  • Blatt 9, 23.06.2016 [pdf]
  • Blatt 10, 30.06.2016 [pdf]
  • Blatt 11, 11.07.2016 [pdf]

Literatur

  1. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  2. Steven Homer and Alan L. Selman, Computability and Complexity Theory, Springer-Verlag, 2011.
  3. Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
  4. Ingo Wegener, Komplexitätstheorie: Grenzen der Effizienz von Algorithmen, Springer-Verlag, 2003.
  5. Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.