Complexity Theory

SS 2006

Schedule

Type Date Location   Organizer
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

Coursework

Lecture Notes

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

Content

Complexity theory classifies algorithmic problems according to the amount of ressources (like time, space, hardware, ...) that are necessary to solve them. In this lecture, we study the most important complexity classes for deterministic, nondeterministic, parallel, and probabilistic computations. Particular attention will be given to the relationships between differrent computation models and to complete problems in the most relevant complexity classes.

Literature

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.

Prerequisites

  • Grundbegriffe zur Berechenbarkeit und Komplexität

Classification

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

Assessment

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

Contact

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