Complexity Theory
Module IN2007
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
Total workload | Contact hours | Credits (ECTS) |
---|---|---|
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
Type | SWS | Title | Lecturer(s) | Dates | Links |
---|---|---|---|---|---|
VI | 6 | Complexity Theory (IN2007) | Ayikudi Ramachandrakumar, B. Ghoshdastidar, D. |
Mon, 10:00–12:00, virtuell Tue, 14:00–16:00, virtuell Thu, 16:00–18:00, virtuell |
eLearning documents |
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: 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.
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.
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.