back to search

Complexity Theory

IN2007Elective Modules Informatics8 ECTSEnglishsummer semesterDepartment Computer Science
AI-edited module sheet. Based on the TUMonline module description, edited for readability.Original in TUMonline

What it is about

You learn formal computational models (in particular Turing machines and circuits) as well as the most important complexity classes (e.g. L, NL, P, NP, PSPACE, EXP, NEXP, PH). By the end you will be able to analyze problems with respect to time and space complexity, apply reductions and completeness proofs, and classify advanced concepts such as alternation, randomized methods, and interactive proof systems.

What you will be able to do

  • Knowledge of Turing machines as a model of computation
  • Understanding of time and space complexity
  • Familiarity with circuits as a model of computation
  • Knowledge of central complexity classes (L, NL, P, NP, PSPACE, EXP, NEXP, PH)
  • Application of reductions and proof of completeness
  • Understanding of diagonalization and the polynomial hierarchy
  • Introduction to alternation, Boolean circuits, randomization and interactive proof systems
  • Ability to analyze new problems with regard to their complexity

What the module consists of

  • LectureConveying theoretical content in lecture and through presentations
  • ExerciseWork on and discussion of exercise sheets; individual feedback through correction

Teaching method

  • Lecture/Presentationfor structured conveyance of concepts
  • Exercise sheets with discussionfor deepening, application and individual feedback
No dates in the current semester
There are no course dates for this module this semester, or they haven't been matched yet.

Module ratings

No ratings for this module yet.

Rate this module

Only fill in the categories you can judge – for each one, either stars and text together or nothing at all.

Lecture
Tutorial
Exam

Official page in TUMonline · Details are not binding.