# Complexity Theory

From International Center for Computational Logic

# Complexity Theory

##### Course with SWS 4/2/0 (lecture/exercise/practical) in WS 2015

**Lecturer**

- Daniel Borchmann, Markus Krötzsch

**Tutor**

**SWS**

- 4/2/0

**Modules**

**Examination method**

- Oral exam

This course covers the fundamental concepts as well as advanced topics of complexity theory.

Key topics are:

**Turing Machines (revision):**Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration**Undecidability:**Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic**Time Complexity:**Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems**Space Complexity:**Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL**Diagonalization:**Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem**Alternation:**Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy**Circuit Complexity:**Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)**Probabilistic Computation:**Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem

### Legacy

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course*Complexity Theory*at the University of Oxford, which were adopted from slides created by Stefan Kreutzer and Ian Horrocks for that course.

**Michael Sipser:***Introduction to the Theory of Computation, International Edition*; 3rd Edition; Cengage Learning 2013

- Introductory text that covers all basic topics in this lecture.

- Erich Grädel:
*Complexity Theory*; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en

- Free lecture notes with general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

- John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*; Addison Wesley Publishing Company 1979

- The
*Cinderella Book*; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

- The

- Christos H. Papadimitriou:
*Computational Complexity*; 1995 Addison-Wesley Publishing Company, Inc

- Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

- Sanjeev Arora and Boaz Barak:
*Computational Complexity: A Modern Approach*; Cambridge University Press 2009

- Extensive book covering the state of the art of Complexity Theory

- Michael R. Garey and David S. Johnson:
*Computers and Intractability*; Bell Telephone Laboratories, Inc. 1979

- The classical book on Complexity Theory; contains a long list of problems with their complexities

Subscribe to events of this course (icalendar)

Lecture | Introduction | DS4, October 14, 2015 in APB E005 | Download |

Lecture | Turing Machines and Languages | DS4, October 16, 2015 in APB E005 | Download |

Lecture | Undecidability | DS2, October 20, 2015 in APB E005 | |

Lecture | Undecidability | DS4, October 21, 2015 in APB E005 | |

Exercise | Mathematical Foundations | DS4, October 23, 2015 in APB E005 | |

Lecture | Rice's Theorem for Recognizability | DS2, October 27, 2015 in APB E005 | |

Lecture | A Hierarchy of Undecidable Problems | DS4, October 28, 2015 in APB E005 | |

Exercise | Turing Machines and Languages | DS4, October 30, 2015 in APB E005 | |

Lecture | The Recursion theorem | DS2, November 3, 2015 in APB E005 | |

Lecture | Decidability and Logic | DS4, November 4, 2015 in APB E005 | |

Exercise | Undecidability and Rice's Theorem | DS4, November 6, 2015 in APB E005 | |

Lecture | Time Complexity: Polynomial Time | DS2, November 10, 2015 in APB E005 | Download |

Lecture | Time Complexity: NP | DS4, November 11, 2015 in APB E005 | Download |

Exercise | The Recursion Theorem and Decidability in Logic | DS4, November 13, 2015 in APB E005 | |

Lecture | Time Complexity: NP Completeness | DS2, November 17, 2015 in APB E005 | Download, Download |

Exercise | Time Complexity | DS4, November 20, 2015 in APB E005 | |

Lecture | NP-Complete Problems | DS2, November 24, 2015 in APB E005 | Download, Download |

Lecture | Space Complexity | DS4, November 25, 2015 in APB E005 | Download, Download |

Exercise | Time Complexity | DS4, November 27, 2015 in APB E005 | |

Lecture | Polynomial Space | DS2, December 1, 2015 in APB E005 | Download, Download |

Lecture | Games/Logarithmic Space | DS4, December 2, 2015 in APB E005 | Download, Download |

Exercise | Space Complexity | DS4, December 4, 2015 in APB E005 | |

Lecture | The Time Hierarchy Theorem | DS2, December 8, 2015 in APB E005 | |

Lecture | More on Hierarchy Theorems, the Gap Theorem | DS4, December 9, 2015 in APB E005 | |

Exercise | Space Complexity | DS4, December 11, 2015 in APB E005 | |

Lecture | Ladner's Theorem | DS2, December 15, 2015 in APB E005 | |

Lecture | The Baker-Gill-Solovay Theorem | DS4, December 16, 2015 in APB E005 | |

Exercise | Mid-Term Consultation | DS4, December 18, 2015 in APB E005 | |

Lecture | Alternating Turing Machines | DS2, January 5, 2016 in APB E005 | Download, Download |

Lecture | Alternating Complexity Classes | DS4, January 6, 2016 in APB E005 | Download, Download |

Exercise | Diagonalization | DS4, January 8, 2016 in APB E005 | |

Lecture | The Polynomial Hierarchy | DS2, January 12, 2016 in APB E005 | Download, Download |

Lecture | Circuit Complexity | DS4, January 13, 2016 in APB E005 | Download, Download |

Exercise | Alternation | DS4, January 15, 2016 in APB E005 | |

Lecture | Circuits for Parallel Computation | DS2, January 19, 2016 in APB E005 | Download, Download |

Lecture | Randomized Computation | DS4, January 20, 2016 in APB E005 | |

Exercise | Circuit Complexity | DS4, January 22, 2016 in APB E005 | |

Lecture | Randomized Computation | DS2, January 26, 2016 in APB E005 | |

Lecture | Randomized Computation | DS4, January 27, 2016 in APB E005 | |

Exercise | Randomized Computation | DS4, January 29, 2016 in APB E005 | |

Lecture | Randomized Computation | DS2, February 2, 2016 in APB E005 | |

Lecture | Wrapup and Outlook | DS4, February 3, 2016 in APB E005 | |

Exercise | Consultation | DS4, February 5, 2016 in APB E005 |

### Calendar