Komplexitätstheorie (Sommersemester 2020)

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

Übungen: Prof. Dr. Markus Müller-Olm, Jens Gutsfeld, Christoph Ohrem

Eintrag für diese Veranstaltung im HIS/LSF

Learnweb-Kurs zu dieser Veranstaltung

Hinweise

  • Wenn Sie an dieser Veranstaltung teilnehmen möchten, tragen Sie sich bitte ab dem 6. April bis spätestens 19. April in den Learnweb-Kurs ein. In diesem Zeitraum wird eine Einschreibung ohne Einschreibeschlüssel möglich sein. Danach erfragen Sie bitte den Einschreibeschlüssel per E-Mail bei einem der Veranstalter.
  • Sollte wegen der Coronakrise auch nach dem 19. April eine Aufnahme des regulären Lehrbetriebs nicht möglich sein, planen wir, Ihnen die Veranstaltung in anderer Form anzubieten. Weitere Hinweise dazu finden Sie  ab dem 14. April im Learnweb-Kurs.

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.