Computational ComplexityModule description #40379 / Version 2
- 9 CP
- Oral exam
- Graded
- Summer semester
- German
This module description is not valid in the current semester (Winter semester 2026/27).
Current version (v9)
| Module / Version | #40379 / #2 |
|---|---|
| Validity | WS 2014/15 – WS 2014/15 |
| Available language(s) | German |
| Credit points | 9 |
| Person responsible for the module | Niedermeier, Rolf |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | German |
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
Participants of this module can classify discrete computational problems according to their computational complexity using standard complexity classes. They understand structural properties of complexity classes and can make qualitative and quantitative statements about computational complexity questions.
The course is principally designed to impart:
technical skills 50x , method skills 50 x ,system skills 0x …,social skills 0x
The course is principally designed to impart:
technical skills 50x , method skills 50 x ,system skills 0x …,social skills 0x
Content
Introduction into structural complexity theory, with particular emphasis on complexity resources time and space.
Particular topics are:
* complexity classes
* theory of the NP-completeness
* hierarchy theorems and polynomial time hierarchy
* interactive proof systems
Particular topics are:
* complexity classes
* theory of the NP-completeness
* 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 | 6 h | 90 h |
| 150 h | |||
Computational Complexity (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 6 h | 90 h |
| 120 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 2-hour tutorials, where an active participation and homework on the work sheets distributed every week is required.
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 | German |
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, Ca mbrid ge 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