Advanced Topics in Complexity Theory

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Advanced Topics in Complexity Theory

Lehrveranstaltung mit SWS 2/2/0 (Vorlesung/Übung/Praktikum) in SS 2016



Umfang (SWS)

  • 2/2/0



  • Mündliche Prüfung


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

Veranstaltungskalender abonnieren (icalendar)

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