Technische Universit├Ąt Ilmenau

Complexity Theory - Modultafeln of TU Ilmenau

The Modultafeln have a pure informational character. The legally binding information can be found in the corresponding Studienplan and Modulhandbuch, which are served on the pages of the course offers. Please also pay attention to this legal advice (german only).
Information on the room and time of planned courses can be found in the e-calendar of events. Courses and examinations that are not listed in the e-calendar of events are planned "by appointment". A list of the events concerned can be found here: courses, examinations.

subject properties Complexity Theory in major Master Mathematik und Wirtschaftsmathematik 2013 (WM)
subject number101053
examination number2400580
departmentDepartment of Mathematics and Natural Sciences
ID of group 2417 (Group for Combinatorics / Graph Theory)
subject leaderProf. Dr. Michael Stiebitz
term Sommersemester
languageDeutsch, bei Nachfrage English
credit points4
on-campus program (h)34
self-study (h)86
Obligationobligatory elective
examoral examination performance, 30 minutes
details of the certificate

werden bei Bedarf festgelet

Signup details for alternative examinations
maximum number of participants
previous knowledge and experience

Lienera Algebra 1, Graphen und Algorithmen

learning outcome

Die Studierenden kennen und beherrschen die gundlegenden Begriffe, Definitionen, Schlussweisen, Methoden und Aussagen der Komplexitätstheorie.


Grundlegende Konzepte der Komplexitätstheorie: Formale Entscheidungsprobleme und Turingmaschinen, Komplexitätsklassen P und NP, Polynomialzeitreduktion, NP-vollständige Entscheidungsprobleme, Der Satz von Cook.

media of instruction

Tafel, Folien, Beamer, Skripte

literature / references

Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness

evaluation of teaching


SS 2016 (Fach)

Freiwillige Evaluation:

SS 2018 (Vorlesung)

SS 2019 (Vorlesung)