Lecture: Complexity Theory
Winter Term 2017/18 in Braunschweig
News
- January 23
- Update on Exercise Sheet 11.
- January 16
- Information on the oral exams can be found below.
- December 12
- Update on Exercise Sheet 8.
- November 6
- The basics on fixed-points can be found in the additional material.
- October 17
- The first exercise class will be at Wednesday, the 25th of October at 13:15 in room IZ 358.
- October 11
- The lecture will start on Tuesday, the 17th of October at 9:45 in room IZ 358.
Oral exams
- We offer appointments for oral exams on February 20 and March 14. (If those are booked out, we will then use February 21 respectively March 13.)
- To book an appointment, please write an email to Peter by February 7. It should contain the name of the lecture, the date, your full name, and your student id ("Matrikelnummer"). If you have any restrictions (e.g. only in the morning or in the afternoon) please also tell us. We will then send you a confirmation.
- If you have three or more oral exam with us, we can also offer an appointment at the end of April (after April 23). This is usually not allowed, but it should be possible if we apply for it. Please contact us in advance.
Organisation
- The lecture will be given by Prof. Roland Meyer and Peter Chini.
- The dates for the lecture are:
-
The date for the exercise classes is:
- Wednesday, 13:15 - 14:45 in IZ 358.
Exercises
The exercise sheets will be made available here. Please hand in your solution in the box next to room 343 in the Institute for Theoretical Computer Science, Muehlenpfordtstr. 23.- Exercise Sheet Uno
- Exercise Sheet Due
- Exercise Sheet Tre
- Exercise Sheet Quattro
- Exercise Sheet Cinque
- Exercise Sheet Sei
- Exercise Sheet Sette
- Exercise Sheet Otto
- Exercise Sheet Nove
- Exercise Sheet Dieci
- Exercise Sheet Undici
Lecture Notes
We offerLecture notes (last updated on October 27, 2016)
that are currently incomplete, but will be updatet on a regular basis. If you have questions or spot a bug in the notes, please contact Pedro.Furthermore, there are handwritten notes for the topics of the course:
- Lower bounds via crossing sequences
- Time and Space Complexity Classes
- Alphabet reduction, tape reduction, compression, speed-up
- Space vs. time, non-determinism vs. determinism
- Savitch's theorem
- Space and time hierarchy results
- Translation theorems
- Immerman and Szelepcsényi's theorem
- Summary of the relationship among the robust complexity classes
- L and NL
- Models of computation for L and NL
- P and NP
- PSPACE
- Alternation
- Alternation (contd.), the polynomial hierarchy
- Oracle Turing machines, relativized complexity classes, and a characterization of the polynomial hierarchy
- Families of Boolean circuits
- Parallel complexity
- Parameterized complexity
- Bounded search trees
- Kernelization
- Principle of inclusion and exclusion
- Iterative compression
- Dynamic programming
- Randomized parameterized algorithms and derandomization (color coding)
- Algebraization
- Fast subset convolution
- Treewidth (Part 1)
- Treewidth (Part 2)
- Hardness in parameterized complexity
Additional Material
- Basics on Fixed-points (Chapter 1 of the script)
- Parameterized complexity
- Scheduling and jump number
- Nemhauser and Trotter's theorem
- Hardness in parameterized complexity
- Advanced topics in parameterized complexity
Module
Sucessfully finishing the module consists of two parts:- Prüfungsleistung: Oral exam after the lecture period.
- Studienleistung: Get at least 60% of all points on your submitted solutions of the exercise sheets.
Contents
- Classical Complexity Theory:
- L and NL
- P and NP
- PSPACE
- Alternation and the Polynomial Hierarchy
- Oracle Turing Machines
- Parameterized Complexity Theory:
- Basics
- Bounded Search Trees
- Dynamic Programming
- Inclusion Exclusion
- Kernelization
- Iterative Compression
- Randomization
- Advanced Algorithmic Techniques in Parameterized Complexity:
- Measure and Conquer
- Treewidth
- Subset Convolution
- Polynomials and Sieves
- Crown Decomposition / Sunflower Lemma / Nemhauser and Trotter
- Cut and Count
- Local Treewidth
- Lower Bounds in Parameterized Complexity Theory:
- Exponential Time Hypothesis
- Intractable Problems and Hardness
Literature
The lectures will be based upon the following books and articles. Most of them are available online, the remaining ones can be found in the library.- M. Sipser: Introduction to the Theory of Computation. International Thomson Publishing, 1996.
- I. Wegener: Complexity Theory. Springer, 2005.
- D.C. Kozen: Automata and Computability. Springer, 1997.
- Goldreich: Computational Complexity. Cambridge, 2008.