de | en

# Complexity Theory

## Module IN2007

This Module is offered by TUM Department of Informatics.

This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.

### Basic Information

IN2007 is a semester module in English language at Bachelor’s level and Master’s level which is offered in summer semester.

This Module is included in the following catalogues within the study programs in physics.

• Catalogue of non-physics elective courses
240 h 90 h 8 CP

### Content, Learning Outcome and Preconditions

#### Content

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.

#### Learning Outcome

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.

#### Preconditions

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

### Courses, Learning and Teaching Methods and Literature

#### Courses and Schedule

VU 6 Complexity Theory (IN2007) Mon, 10:00–12:00, MI 03.09.014
Tue, 14:00–16:00, MI 02.13.010
Wed, 08:00–10:00, MI 02.13.010

#### Learning and Teaching Methods

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.

#### Media

Slides, whiteboard, homework assignments

#### Literature

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, 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.

### Module Exam

#### Description of exams and course work

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.

#### Exam Repetition

The exam may be repeated at the end of the semester.

Top of page