Workload:
180 h
|
Module Number INF3421 |
Module Title Complexity Theory |
Type of Module Elective Compulsory |
|---|---|---|
| ECTS | 6 | |
|
Work load - Contact time - Self study |
Workload:
180 h Class time:
60 h / 4 SWS Self study:
120 h |
|
| Duration | 1 Semester | |
| Frequency | In the winter semester | |
| Language of instruction | German | |
| Type of Exam | Written exam (in case of a small number of participants: oral tests) |
|
| Lecture type(s) | Lecture | |
| Content | Topics include complexity measures and their basic relationships, hierarchy theorems, reduction and completeness, alternation and circuits, the polynomial hierarchy, and complexity of approximability issues. |
|
| Objectives | The students have an overview of the structure of the most important complexity classes and therefore a frame of reference for the complexity classification of combinatorial problems. They have developed an awareness of the seemingly notorious difficulty of combinatorial problems and the formal uncertainty of this situation. |
|
| Allocation of credits / grading |
Type of Class
Status
SWS
Credits
Type of Exam
Exam duration
Evaluation
Calculation
of Module (%) |
|
| Prerequisite for participation | There are no specific prerequisites. | |
| Lecturer / Other | Klost | |
| Literature | Hopcroft u. Ullman, Introduction to automata theory, languages and computation, 1979 Rogers, The theory of recursive functions and effective computability, 1989 Arora and Barak. Computational complexity: a modern approach, 2009. |
|
| Last offered | unknown | |
| Planned for | Wintersemester 2025 | |
| Assigned Study Areas | BIOINFM2510, INFM2510, INFM3410, MDZINFM2510, MEINFM3210 | |