Stud.IP Uni Oldenburg
University of Oldenburg
01.10.2020 15:52:33
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
Faculty/Institute Department of Computing Science
Used in course of study
  • Master's Programme Computing Science (Master) > Theoretische Informatik
Contact person
Module responsibility
Authorized examiners
Entry requirements
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 AC (Aufbaucurriculum / Composition)
Modulart je nach Studiengang Pflicht oder Wahlpflicht
Lern-/Lehrform / Type of program
Vorkenntnisse / Previous knowledge
Course type Comment SWS Frequency Workload attendance
Lecture 2.00 SuSe 28 h
Exercises 2.00 SuSe 28 h
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