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 | Lange | |
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 | currently not planned | |
Assigned Study Areas | BIOINFM2510, INFM2510, INFM3410, MDZINFM2510, MEINFM3210 |