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
News
- 21.10.2014: First lecture
Contents
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
Organization
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
Forum
For this lecture a forum is available. Here, substantive and organizational questions can be discussed. A registration is not necessary.
Details
Date | Contents | Board | Exercise | Recording | Literature |
21.10.2014 | Introduction, problems, finite automata | mkv | 1,2 | ||
23.10.2014 | Memory, Single tape machine | mkv | 1 | ||
28.10.2014 | Time classes, linear speedup, Universal Turing machine | mkv | 1,2,3 | ||
30.10.2014 | Non-determinism / 1st exercise | mkv | 1,2,3 | ||
04.11.2014 | Closure properties, canonic computation trees | mkv | 2,4 | ||
06.11.2014 | BH, PP / 2nd exercise | mkv | 2,4 | ||
11.11.2014 | R, co-R, ZPP, BPP, Theorem of Savitch, ATM | mkv | 1,2,4 | ||
13.11.2014 | ATIME, PH | mkv | 1,2 | ||
18.11.2014 | Reductions, Oracle TMs, P^NP |
| mkv | 2 | |
20.11.2014 | 3rd Exercise (two hours) | ||||
25.11.2014 | Completeness and Hardness | mkv | 2 | ||
27.11.2014 | Circuit Complexity | mkv | 1,5 | ||
02.12.2014 | 4th exercise (two hours) | ||||
04.12.2014 | Circuit Size | mkv | 5 | ||
09.12.2014 | Formula Size, Depth, | mkv | 5 | ||
11.12.2014 | BPP in P/Poly, Circuit Families | mkv | 5 | ||
16.12.2014 | NC, L, NL, AC | mkv | 1,2 | ||
18.12.2014 | NL = co-NL / 5th exercise | mkv | 2 | ||
23.12.2015 | Circuit Width, Reversal Complexity | * | * | ||
08.01.2015 | IP = PSPACE | mkv | 2 | ||
13.01.2015 | IP = PSPACE | mkv | 2 | ||
15.01.2015 | 6th exercise | ||||
20.01.2015 | IP revisited, Average-P | mkv | 2,6,7 | ||
22.01.2015 | DisNP | mkv | 6,7 | ||
27.01.2015 | DisNP-Complete Problems NBH | mkv | 8 | ||
29.01.2014 | Quantum Circuits | mkv | 8 | ||
03.02.2015 | QP | mkv | 8 | ||
05.02.2015 | 7th exercise | 8 | |||
10.02.2015 | QP versus PP | mkv | 8 | ||
12.02.2015 | Survey & research topics |
Exam
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.
Literature
- Rüdiger Reischuk: Einführung in die Komplexitätstheorie. Teubner Verlag Stuttgart, Leipzig, 1990.
- Michael Sipser: Introduction to the Theory of Computation, Cengage Learning, 2012
- Christos Papadimitriou: Computational Complexity, John Wiley, 2003
- The Complexity Zoo (https://complexityzoo.uwaterloo.ca/Complexity_Zoo)
- Ingo Wegener, The Complexity of Boolean Functions, Wiley, 1987
- Lecture notes of "Average-Komplexitätstheorie und Average-Analyse von Algorithmen", 2004, pdf
- Average-Case Complexity Forum
- Lecture Notes of MIT-Opencouseware "Quantum Complexity Theory", Scott Aaronson
- Further references will be published here during the lecture.