Computational ComplexityModule description #40379 / Version 5
- 9 CP
- Oral exam
- Graded
- Summer semester
- English
This module description is not valid in the current semester (Winter semester 2026/27).
Current version (v9)
| Module / Version | #40379 / #5 |
|---|---|
| Validity | SS 2016 – WS 2016/17 |
| Available language(s) | English |
| Credit points | 9 |
| Person responsible for the module | Niedermeier, Rolf |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | English |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34351100 FG Algorithmik und Komplexitätstheorie (AKT) |
Contact
| Office | EN 23 |
|---|---|
| Contact person | Thielcke, Christlinde |
| E-mail address | lehre@akt.tu-berlin.de |
| Website | https://www.tu.berlin/akt/studium-lehre/lehrveranstaltungen |
Learning outcomes
On successful completion, students will be able to:
- estimate the computational costs for solving fundamental problems
- classify discrete computational problems according to their computational complexity using reductions and standard complexity classes
- understand structural properties of complexity classes
- make qualitative and quantitative statements about computational complexity questions
- estimate the computational costs for solving fundamental problems
- classify discrete computational problems according to their computational complexity using reductions and standard complexity classes
- understand structural properties of complexity classes
- make qualitative and quantitative statements about computational complexity questions
Content
Introduction into structural complexity theory, with particular emphasis on complexity resources time and space.
Particular topics are:
- complexity classes
- reductions between problems
- theory of the NP-completeness and the P vs. NP question
- hierarchy theorems and polynomial time hierarchy
- interactive proof systems
Particular topics are:
- complexity classes
- reductions between problems
- theory of the NP-completeness and the P vs. NP question
- hierarchy theorems and polynomial time hierarchy
- interactive proof systems
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Computational Complexity (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 5 h | 75 h |
| 135 h | |||
Computational Complexity (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 5 h | 75 h |
| 105 h | |||
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Prüfungsvorbereitung | 1 | 30 h | 30 h |
| 30 h | |||
The workload of the module adds up to 270 hours. The module therefore comprises 9 credit points.
Description of teaching and learning methods
There is a lecture 4 hours per week presenting the whole course material. The lectures are accompanied by tutorials in which distributed work sheets are solved together.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
a) obligatory: Basic course on automata and complexity
b) desirable: Basic knowledge on algorithms
b) desirable: Basic knowledge on algorithms
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | English |
Exam description
Final oral exam determining the grade (MP).
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Please register at QISPOS or directly at the examination office.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
- Christos H. Papadimitriou: Computational Complexity, Addison Wesley, 1994.
- Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009
Assigned programs
This module is not used in any program.
Computer Science Master with focus “Reliable Systems”
Computer Science diploma
Technical Computer Science Master with focus “Software Engineering”
Technical Computer Science diploma
Computer Science diploma
Technical Computer Science Master with focus “Software Engineering”
Technical Computer Science diploma
Miscellaneous
Not specified