Stud.IP Uni Oldenburg
University of Oldenburg
18.10.2021 19:47:54
inf451 - Complexity Theory (Complete module description)
Original version English Download as PDF
Module label Complexity Theory
Module code inf451
Credit points 6.0 KP
Workload 180 h
Institute directory Department of Computing Science
Applicability of the module
  • Master's Programme Computing Science (Master) > Theoretische Informatik
Responsible persons
Best, Eike (Authorized examiners)
Lehrenden, Die im Modul (Authorized examiners)
Skills to be acquired in this module
This module covers the computational complexity of algorithms. Complexity considerations are concerned with the time, the memory, and the parallelism required or allowed, for solving an algorithmic problem. In particular, one is interested in lower and/or upper time and space bounds, and in approximative investigations providing information about entire classes of algorithms. For any concrete problem, complexity theory aims at being able to find out which class it belongs to, and thus estimating the cost of the most efficient methods of solving it. Methods taught in this module are general, not depending on any particular algorithmic model or chosen programming language.

Professional competence
The students:
  • use Turing machines and variants thereof
  • define time, memory, and processor requirements of algorithmic problems
  • specify the most relevant complexity classes
  • estimate the computational complexity of the most important problems

Methodological competence
The students:
  • analyse the complexity of algorithms
  • apply techniques of simulation, reduction, and diagonalisation
  • compare new problems in terms of complexity

Social competence
The students:
  • present proof sketches, proofs, and algorithmic solutions in front of an audience
Module contents
  • Mathematical foundations
  • Turing machines and register machines
  • Space and time hierarchies, equivalence and hierarchy theorems
  • Complexity classes: P, NP, NPC, PSPACE, and others
  • Alternating automata and polynomial time hierarchy
  • Circuit complexity
Reader's advisory
  • Eike Best: Skript zur Vorlesung (2015)
  • Michael R. Garey, David S. Johnson: Computers and Intractability.Freeman, New York (2003).
  • Steven Homer, Alan L. Selman: Computability and Complexity Theory. Springer (2000).
  • John E. Hopcroft, Jeffrey D. Ullmann: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).
  • Rüdiger Reischuk: Komplexitätstheorie. 2. Auflage. Teubner, Stuttgart/Leipzig (1999).
  • Michael Sipser: Introduction to the Theory of Computation. Third Edition, Cengage (2005).
Language of instruction German
Duration (semesters) 1 Semester
Module frequency unregelmäßig
Module capacity unlimited
Modullevel / module level AC (Aufbaucurriculum / Composition)
Modulart / typ of module je nach Studiengang Pflicht oder Wahlpflicht
Lehr-/Lernform / Teaching/Learning method
Vorkenntnisse / Previous knowledge
Course type Comment SWS Frequency Workload of compulsory attendance
2 SuSe 28
2 SuSe 28
Total time of attendance for the module 56 h
Examination Time of examination Type of examination
Final exam of module
At the end of the lecture period
exercises and oral exam