Advanced Topics in Complexity Theory

From International Center for Computational Logic

Advanced Topics in Complexity Theory

Course with SWS 2/2/0 (lecture/exercise/practical) in SS 2016




  • 2/2/0


Examination method

  • Oral exam


This lecture discusses some advanced topics of complexity theory. Currently planned topics are

  • Approximation Complexity
  • Interactive Proof Systems
  • Counting Complexity

The course will be self-contained, but some prior knowledge about the fundamental notions of complexity theory is required. Additional prerequisites will be discussed in the exercises.


Approximation Complexity

Computational complexity tries to assess the complexity of solving problems. Usually, those problems are represented as decision problems. However, for practical applications, it is often more convenient to consider optimization problems, where solutions are sought that minimize or maximize a certain objective function.

Clearly, solving optimization problems is not easier than solving the corresponding decision problem. On the other hand, for optimization problems we can ask for approximate solutions whose value is within a certain range of the optimal value. This gives rise to the rich field of Approximation Algorithms. In this lecture, we shall introduce the basic notions of approximation algorithms and discuss some classical examples.

Intuitively, approximating the solution of a problem "could" be easier than solving the real problem. However, it has been shown that for some problems computing an approximate solution within a certain bound of the optimal value is NP-hard. While this can be shown for some problems directly, a much deeper result is needed to show this for a wide range of problems. This result is the famous PCP-Theorem stating a characterization of NP in terms of probabilistically checkable proofs with. We shall state this theorem and show how it relates to the hardness of approximation of certain problems.

Interactive Proof Systems

Among the many possible definitions of the complexity class NP, the following characterization based on computation by interaction is one of the most interesting: a language L is in NP if and only if there exist a prover P and a polynomial-time verifier V such that

  • if x ∈ L, then P can send a proof to V of polynomial length that V will accept, and
  • if x ∈ L, then whatever proof of polynomial length P sends to V, it will be rejected.

This definition gives inspiration to new complexity classes based on computation by interaction, such as interactive proof systems (IP), Merlin-Arthur protocols (MA and AM), and Multiprover interactive protocols (MIP). In those protocols, the prover always has unrestricted computation power (Merlin), while the verifier does not (Arthur). However, the verifier is allowed to be correct with high probability (i.e., in BPP). It is interesting to see how this approach allows to view computation in a new and fruitful way: the developments in interactive protocols finally lead to the discovery of the PCP Theorem.

In this part of the lecture, we shall investigate the power of these alternative approaches to computation. We shall see that some famous problems can be characterized nicely using interactive proofs systems. In addition, we shall show that IP = PSpace, and we also shall discuss MIP = NExpTime. Finally, if time permits, we shall also investigate the connection between interactive protocols and cryptography, in particular zero knowledge proofs.

Counting Complexity

Sometimes knowing whether a solution exists or not is not sufficient. Instead, one may be interested in the exact number of solution a problem has. This is for example the case if one wants to estimate probabilities by random sampling.

In complexity theory, this is formalized by the notion of counting problems. The corresponding class #P contains problems like #SAT and #CYCLE, which ask for the number of satisfying assignments or for the number of cycles in a directed graph, respectively. It is clear that when we can solve the counting version of a problem, we can also solve it decision variant. However, the converse does not seem to be true: while we can decide in polynomial time whether a directed graph has a cycle, it is true that if we can solve #CYCLE in polynomial time, then P = NP.

In this part of the lecture, we shall investigate counting problems in more detail. We shall see that there are natural connections to randomized complexity classes like PP. We shall discuss the notion of #P-complete problems, and shall show that (not surprisingly) #SAT of one of those problems. In addition, we shall also prove Valiant's Theorem that computing the permanent of a 0-1 matrix is also #P-complete. Finally, we shall discuss the proof (maybe not in detail) of Toda's Theorem that every problem in the polynomial hierarchy can be solved in polynomial time with access to an oracle for #SAT.


  • Michael Sipser: Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2013
  • Christos H. Papadimitriou: Computational Complexity, 1st edition, Addison-Wesley, 1994
  • Sanjeev Arora and Boaz Barak: Computational Complexity A Modern Approach, Cambridge University Press, 2009

Lecture Notes and Exercise Sheets

Subscribe to events of this course (icalendar)

Lecture Introduction DS5, April 4, 2016 in APB E005
Exercise General Revision DS3, April 5, 2016 in APB E005
Lecture Function Problems DS5, April 11, 2016 in APB E005
Exercise Revision Randomized Computation DS3, April 12, 2016 in APB E005
Lecture Approximation Algorithms DS5, April 18, 2016 in APB E005
Exercise Function Problems DS3, April 19, 2016 in APB E005
Lecture Approximation Algorithms / Approximation and Complexity DS5, April 25, 2016 in APB E005
Exercise Revision Circuits DS3, April 26, 2016 in APB E005
Lecture Approximation and Complexity DS5, May 2, 2016 in APB E005
Lecture Non-Approximability DS5, May 9, 2016 in APB E005
Exercise Approximation and Complexity DS3, May 10, 2016 in APB E005
Lecture Interactive Proof Systems with Deterministic and Probabilistic Verifiers DS5, May 23, 2016 in APB E005
Exercise Optimization Problems DS3, May 24, 2016 in APB E005
Lecture IP is part of PSpace DS5, June 6, 2016 in APB E005
Exercise Interactive Proofs DS3, June 7, 2016 in APB E005
Lecture Public Coin Protocols DS5, June 13, 2016 in APB E005
Exercise An Interactive Protocol for the Permanent DS3, June 14, 2016 in APB E005
Lecture #SAT_D ∈ IP DS5, June 20, 2016 in APB E005
Lecture TQBF ∈ IP, Counting Complexity DS5, June 27, 2016 in APB E005
Exercise Details on the Proof of the GNI ∈ AM DS3, June 28, 2016 in APB E005
Lecture Counting Complexity DS5, July 4, 2016 in APB E005
Exercise NP-completeness of GI implies the collapse of PH DS3, July 5, 2016 in APB E005
Lecture Valiant's Theorem DS5, July 11, 2016 in APB E005