Literatur | Links  

Komplexitätstheorie

Vorlesung

Einführung

Eine Beschränkung wichtiger Ressourcen wie Laufzeit und Speicherplatz auf realistische Dimensionen führt zu einer drastischen Einschränkung der Klasse lösbarer Probleme. Um dieses Phänomen zu studieren, wird, bei fixierten Ressourcen, die Komplexitätsklasse aller Probleme eingeführt, die innerhalb dieser Ressourcen lösbar sind. Wichtige Komplexitätsklassen wie Logspace, NC, P, NP und PSPACE werden eingeführt und ihre Eigenschaften werden untersucht. In der Veranstaltung wird sodann eine Auswahl der folgenden Themengebiete behandelt: Lernziele: Neben dem Verständnis der durch Ressourcenschranken bedingten Grenzen der algorithmischen Lösbarkeit ist die Fähigkeit, die Komplexität spezieller Probleme einzuschätzen und ein fundiertes Gefühl für das Machbare zu entwickeln, das wesentliche Ziel der Veranstaltung.

Kürzel laut Studienordnung: M-KTH.  Creditpoints: 8.  SWS: 3V, 2Ü.

Literatur

[AB] Sanjeev Arora and Boaz Barak. Computational Complexity. A Modern Approach. Cambridge University Press, 2009.
[G] Oded Goldreich. Computational Complexity. A Conceptual Perspective. Cambridge University Press, 2008.
[P] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1995.
[W] Ingo Wegener. Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer-Verlag, 2003.
[AB] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006.
[HU] J. E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[S] Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009.
[K] Dexter Kozen. Theory of Computation. Springer-Verlag, 2006.
[V] Heribert Vollmer. Introduction to Circuit Complexity. Springer-Verlag, 1999.

Links

[LF-Blog] Lance Fortnow's Computational Complexity Blog
[RJL-Blog] Richard J. Lipton's Theory of Computation Blog
[CCC] IEEE Conference on Computational Complexity (CCC)