You are here: Home Lehre Frühere Veranstaltungen Universität Freiburg Computational Complexity
Document Actions

Computational Complexity

Advanced topics of computational complexity, including the following animals from the complexity zoo: P, NP, PSPACE, co-NP, AC, NC, L, NL, BH, IP, Av-P, Dis-NP, #P.

Special lecture in the specialization Information Systems


  • 21.10.2014: First lecture


After an introduction into the world of computational complexity we discuss the following topics.

  • Countability, enumerable sets, machine models, computational classes
  • Types of reductions, generic complete problems
  • Random complexity classes
  • Circuit complexity
  • Below linear time
  • Beyond polynomial time
  • Average complexity classes
  • Quantum computing
  • Communication games
  • Information complexity
  • Kolmogorov complexity 


Lecture & Exercises

  • Christian Schindelhauer
    • Tuesday, 10:00 - 12:00 c.t., Room 101-01-016
    • Thursday, 10:00 - 12:00 c.t., Room 101-01-016


For this lecture a forum is available. Here, substantive and organizational questions can be discussed. A registration is not necessary. 


Date Contents Board Exercise RecordingLiterature
21.10.2014 Introduction, problems, finite automata  pdf   mkv1,2
23.10.2014 Memory, Single tape machine  pdf   mkv1
28.10.2014 Time classes, linear speedup, Universal Turing machine  pdf   mkv1,2,3
30.10.2014 Non-determinism / 1st exercise  pdf  pdf mkv1,2,3
04.11.2014 Closure properties, canonic computation trees pdf    mkv2,4
06.11.2014 BH, PP / 2nd exercise  pdf    pdf mkv2,4
11.11.2014 R, co-R, ZPP, BPP, Theorem of Savitch, ATM  pdf   mkv1,2,4
13.11.2014 ATIME, PH  pdf   mkv1,2
18.11.2014 Reductions, Oracle TMs, P^NP pdf 


20.11.2014 3rd Exercise (two hours)    pdf   
25.11.2014  Completeness and Hardness pdf   mkv2
27.11.2014 Circuit Complexity pdf    mkv1,5
02.12.2014 4th exercise (two hours)    pdf   
04.12.2014 Circuit Sizepdf    mkv 5
09.12.2014 Formula Size, Depth,  pdf   mkv 5
11.12.2014  BPP in P/Poly, Circuit Families  pdf   mkv 5
16.12.2014 NC, L, NL, AC pdf    mkv 1,2
18.12.2014  NL = co-NL / 5th exercise pdf   pdf mkv 2

Circuit Width, Reversal Complexity

  *   * 
08.01.2015  IP = PSPACE    pdf   mkv 2
13.01.2015 IP = PSPACE  pdf    mkv 2
15.01.2015 6th exercise   pdf   
20.01.2015 IP revisited, Average-P pdf    mkv 2,6,7
22.01.2015 DisNP  pdf    mkv 6,7
27.01.2015 DisNP-Complete Problems NBH pdf    mkv 8
29.01.2014 Quantum Circuits   pdf    mkv 8
03.02.2015 QP  pdf   mkv 8

7th exercise

   pdf   8
10.02.2015  QP versus PP pdf    mkv  8
12.02.2015 Survey & research topics        




There will be an oral exam in the examination period (*The lecture from 23.12.2014 is not relevant for the oral exam). Please register on-line using the campus management system. There are no requirements for the registration and please observe the registration deadline.



  1. Rüdiger Reischuk: Einführung in die Komplexitätstheorie. Teubner Verlag Stuttgart, Leipzig, 1990.
  2. Michael Sipser: Introduction to the Theory of Computation, Cengage Learning, 2012
  3. Christos Papadimitriou: Computational Complexity, John Wiley, 2003
  4. The Complexity Zoo (https://complexityzoo.uwaterloo.ca/Complexity_Zoo)
  5. Ingo Wegener, The Complexity of Boolean Functions, Wiley, 1987
  6. Lecture notes of "Average-Komplexitätstheorie und Average-Analyse von Algorithmen", 2004, pdf
  7. Average-Case Complexity Forum 
  8. Lecture Notes of MIT-Opencouseware "Quantum Complexity Theory", Scott Aaronson
  9. Further references will be published here during the lecture.


Personal tools