Advanced Topics in Complexity Theory
Advanced Topics in Complexity Theory
Course with SWS 2/2/0 (lecture/exercise/practical) in SS 2016
Lecturer
Tutor
SWS
- 2/2/0
Modules
Examination method
- Oral exam
Overview
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.
Details
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.Books
- 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 |
Calendar
