Complexity Theory

First, Turing Machines are covered thoroughly. Time and space complexity are studied. Moreover, circuits as computational models are investigated. The complexity classes L, NL, P, NP, PSPACE, EXP, NEXP, PH are introduced. Afterwards, completeness and fundamental structural relationships between complexity classes are established. Furthermore, the concept of alternation, Boolean Circuits, randomization and interactive proof systems are covered in the module.

The students know the important methods of the complexity theory. They have knowledge of computational models, complexity classes, reductions and completeness. Moreover, they have a profound knowledge of advanced concepts such as diagonalization, the polynomial hierarchy, space complexity, alternation, Boolean circuits, randomization and interactive proof systems. Furthermore, they can apply the appropriate methods and concepts to analyze new problems in their complexity.

IN0011 Introduction to Theory of Computation, IN0015 Discrete Structures, IN0007 Fundamentals of Algorithms and Data Structures

The module consists of lectures and tutorials. The content of the lectures is conveyed by presentations of the scientific material. In solving homework assignments, the students are encouraged to work intensively on the respective topics. The solutions of the assignments are discussed in the tutorials. The homework assignments are graded so that students get an individual feedback on their learning success.

Slides, whiteboard, homework assignments

Sanjeev Arora, Boaz Barak: Computational Complexity - A Modern Approach. Cambridge University Press: Cambridge-New York-Melbourne, 2009.
Giorgio Ausiello, Pierluigi Creszenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi: Complexity and approximation - Combinatorial optimization problems and their approximability properties. Springer-Verlag: Berlin-Heidelberg, 1999.
Jose L. Balcazar, Josep Diaz, Joaquim Gabarro: Structural Complexity I (and II). EATCS Monographs on Theoretical Computer Science, Springer-Verlag: Berlin-Heidelberg, 1995.
Christos H. Papadimitriou: Computational Complexity. Addison-Wesley Publishing Company: London-Amsterdam-New York, 1994.
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Englewood Clis, NJ, 1982.
Karl Rudiger Reischuk: Komplexitätstheorie - Band I: Grundlagen. B.G. Teubner: Stuttgart-Leipzig, 1999.
Michael Sipser: Introduction to the Theory of Computation. International Edition, Thomson Course Technology: Australia-Canada-Mexico-Singapore-Spain-United Kingdom-United States, 2006.
Ingo Wegener: The complexity of Boolean functions. Wiley-Teubner Series in Computer Science: Stuttgart-Chichester-New York, 1987.

The exam takes the form of a 120 minutes written test. In the written exam, based on the questions posed, the students are intended to prove that they have fundamental and advanced knowledge in the area of complexity theory. The students demonstrate that they are able to recognize and analyze problems in complexity theory and to find efficient solutions within a limited scope of time.