Komplexitätstheorie

SS 2006

Termine

Art Termin Ort   Veranstalter
V4 Di 10:00 - 11:30 AH I 4. April E. Grädel
Fr. 10:00 - 11:30 AH I 21. April E. Grädel
Ü2 Mi 17:15 - 18:45 5056 12. April E. Grädel

Übungen

Skript

  • Kapitel 1: Turingmaschinen und deterministische Komplexitätsklassen [ps] [pdf]
  • Kapitel 2: Nichtdeterministische Komplexitätsklassen [ps] [pdf]
  • Kapitel 3: NP-vollständige Probleme [ps] [pdf]
  • Kapitel 4: PSPACE und die polynomiale Hierarchie [ps] [pdf]
  • Kapitel 5: Paralelle Berechnungsmodelle I: Alternierende Turingmaschinen [ps] [pdf]
  • Kapitel 6: Paralelle Berechnungsmodelle II: Schaltkreise [ps] [pdf]
  • Kapitel 7: Komplexitätstheorie für Optimierungsprobleme [ps] [pdf]
  • Kapitel 8: Komplexitätstheorie für probabilistische Algorithmen – erweiterte Fassung, mit Artus-Merlin-Spielen [ps] [pdf]

Inhalt

Die Komplexitätstheorie klassifiziert algorithmische Probleme aufgrund der zur ihrer Lösung benötigten Ressourcen (wie Rechenzeit, Speicherplatz, Hardware, ....). In der Vorlesung werden die wichtigsten Komplexitätsklassen für deterministische, nichtdeterministische, parallele und probabilistische Berechnungen behandelt. Von besonderer Bedeutung sind die Zusammenhänge zwischen verschiedenen Berechnungsmodellen und vollständige Probleme in den wichtigsten Komplexitätsklassen.

Literatur

Einführende Literatur

[1] D. P. Bovet and P. Crescenzi. Introduction to the theory of complexity. Prentice Hall, New York, 1994.
[2] M. Garey and D. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company, New York, 1979.
[3] O. Goldreich. Introduction to Complexity Theory. Mitschrift einer Vorlesung, 1999.
[4] J. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2000.
[5] C. Papadimitriou. Computational complexity. Addison-Wesley, 1994.
[6] K. R. Reischuk. Einführung in die Komplexitätstheorie. Teubner, Stuttgart, 1990.
[7] M. Sipser. Introduction to the theory of computation. PWS Publishing, Boston, 1997.
[8] I. Wegener. Grenzen der Effizienz von Algorithmen. Springer-Verlag, Berlin u.a., 2003.
[9] C. K. Yap. Introduction to complexity classes. Oxford University Press, to appear.

Weiterführende Literatur

[1] P. Bürgisser, M. Clausen, and M. Shokrollahi. Algebraic Complexity Theory. Springer-Verlag, 1997.
[2] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.
[3] J. Balcazar, J. Diaz, and J. Gabarro. Structural complexity. Springer-Verlag, 1988.
[4] P. Crescenzi and V. Kann. A compendium of NP optimization problem. Online edition, 1995.
[5] R. Downey and M. Fellows. Parametrized complexity. Springer-Verlag, 1999.
[6] R. Greenlaw, H. J. Hoover, and L. Ruzzo. Limits to parallel computation: P-completeness theory. Oxford University Press, 1995.
[7] J. Hartmanis. Feasible computations and provable complexity properties. SIAM, Philadelphia, 1978.
[8] J. Hromkovic. Communication complexity and parallel computing. Springer-Verlag, 1997.
[9] N. Immerman. Descriptive complexity. Springer-Verlag, 1999.
[10] D. Johnson. Handbook of Theoretical Computer Science (J. V. Leeuwen, ed.). Elsevier Science Publishers B.V., 1990.
[11] E. Mayr, H. J. Prömel, and A. Steger (Eds.). Lectures on proof verification and approximation algorithms. Springer-Verlag, 1998.
[12] K. Wagner and G. Wechsung. Computational complexity. Reidel, 1986.
[13] I. Wegener. The complexity of Boolean functions. Teubner, Stuttgart, 198.

Voraussetzungen

  • Grundbegriffe zur Berechenbarkeit und Komplexität

Zuordnung

  • Informatiker: Theoretische Informatik, Vertiefungsfach
  • Mathematiker: Angewandte Mathematik
  • Lehramtskandidaten: Angewandte Mathematik (D)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science
  • Sonstige: Informatik

Leistungsnachweis

  • Informatiker und Mathematiker: Übungsschein bei aktiver Teilnahme an den Übungen
  • Software Systems Engineering (M.Sc.): active participation in exercises and final examination

Rückfragen

Erich Grädel, Vince Bárány, Tobias Ganzow, Łukasz Kaiser