Komplexitätstheorie (Sommersemester 2018)

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

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

Eintrag für diese Veranstaltung im HIS/LSF

Learnweb-Kurs zu dieser Veranstaltung

Ort und Zeit

  • Vorlesung: Di, 10:15-11:45 Uhr, M6 und Fr, 10:15-11:45 Uhr, M6.
  • Übungen: Mi, 10:15-11:45 Uhr, M6.

Hinweise

  • Aktuelle Informationen, Folien und Übungsblätter zu dieser Veranstaltung werden im zugehörigen Learnweb-Kurs veröffentlicht. Zum Login auf der Learnweb-Plattform genügt Ihre ZIV-Benutzerkennung mit Passwort; der Einschreibeschlüssel zum Zugriff auf diesen Kurs wird in der ersten Vorlesung bekannt gegeben.

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

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, 2013.
  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, 1993.