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