-
Time Complexity
- P, NP, NP-completeness.
-
Space Complexity
- Savitch's theorem, games.
- NL, Immerman and Szlepcseny's theorem.
-
Diagonalization
- Hierarchy theorems
- Ladner's theorem.
-
Parameterized Complexity
- Graphs of bounded tree width.
- Courcelle's theorem.
- Hardness theory.
-
Polynomial Hierarchy
- Definition and complete problems.
- Alternation.
- Collapse
-
Circuits
- P/poly.
- Karp and Lipton's theorem.
- Lower bounds.
- NC and parallel computing.
-
Randomness
- BPP.
- Adleman's theorem.
- Sipser and Gac's theorem.
-
Countin
- P.
- Approximate counting.
- Toda's theorem.
-
Communication Complexity
- Fooling sets.
-
Logic in Complexity Theory
- Alternative definitions of complexity classes.
- Theories.
Module INF-56-53-M-5
Complexity Theory (M, 8.0 LP)
Module Identification
Module Number | Module Name | CP (Effort) |
---|---|---|
INF-56-53-M-5 | Complexity Theory | 8.0 CP (240 h) |
Basedata
CP, Effort | 8.0 CP = 240 h |
---|---|
Position of the semester | 1 Sem. in WiSe |
Level | [5] Master (Entry Level) |
Language | [EN] English |
Module Manager | |
Lecturers | |
Area of study | [INF-ALG] Algorithmics and Deduction |
Reference course of study | [INF-88.79-SG] M.Sc. Computer Science |
Livecycle-State | [NORM] Active |
Courses
Type/SWS | Course Number | Title | Choice in Module-Part | Presence-Time / Self-Study | SL | SL is required for exa. | PL | CP | Sem. | |
---|---|---|---|---|---|---|---|---|---|---|
4V+2U | INF-56-53-K-5 | Complexity Theory
| P | 84 h | 156 h |
U-Schein
| ja | see comments | 8.0 | WiSe |
- About [INF-56-53-K-5]: Title: "Complexity Theory"; Presence-Time: 84 h; Self-Study: 156 h
- About [INF-56-53-K-5]: The study achievement [U-Schein] proof of successful participation in the exercise classes (ungraded) must be obtained. It is a prerequisite for the examination .
Examination achievement PL1
- Form of examination: written or oral examination
- Examination Frequency: each winter semester
- Examination number: 65653
("Complexity Theory")
Type of examination will be announced in the lecture. Duration of the examination: ref. examination regulations.
Evaluation of grades
The grade of the module examination is also the module grade.
Contents
Competencies / intended learning achievements
Upon successful completion of the module, students will be able to
- explain concepts and methods of complexity theory,
- explain the importance of complexity boundaries for real problems,
- and to classify algorithmic problems in terms of their complexity classes.
Literature
- Downey, Rodney G., and Michael R. Fellows. Fundamentals of parameterized complexity. Vol. 4. London: Springer, 2013.
- Hopcroft, John E., Jeffrey D. Ullman, and Rajeev Motwani. Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Vol. 2. Deutschland, München: Pearson Studium, 2002.
- Papadimitriou, Christos H. Computational complexity. John Wiley and Sons Ltd., 2003.
- Reischuk, Karl Rüdiger. Einführung in die Komplexitätstheorie. BG Teubner, 1990.
- Sipser, Michael. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.
Further literature will be announced in the lecture.
Requirements for attendance (informal)
None
Requirements for attendance (formal)
None
References to Module / Module Number [INF-56-53-M-5]
Course of Study | Section | Choice/Obligation |
---|---|---|
[INF-88.79-SG] M.Sc. Computer Science | Computer Science Theory | [WP] Compulsory Elective |
[INF-88.79-SG] M.Sc. Computer Science | Formal Fundamentals | [WP] Compulsory Elective |
[INF-88.79-SG] M.Sc. Computer Science | Specialization 1 | [WP] Compulsory Elective |
[MAT-88.105-SG] M.Sc. Mathematics | Subsidiary Topic (Minor) | [WP] Compulsory Elective |
Module-Pool | Name | |
[INF-Alg_Ba_V-MPOOL-4] | Specialization Bachelor TA Algorithmics and Deduction | |
[MV-MBINFO-MPOOL-6] | Wahlpflichtmodule Maschinenbau mit angewandter Informatik |