Computational Complexity (Spring 2015)

This course describes attempts to answer a fundamental question of CS namely: What can computers solve efficiently?

Some Bibliography:

While the course does not follow one book in a precise order, most of the material can be found in the following two books (that are available online). I will point to relevant section in the books when teaching the material.

• Draft of book by Sanjeev Arora and Boaz Barak.
• Draft of book by Oded Goldreich.

Some of the topics (at least in the beginning of the course) are also covered in the following books.

• Computational Complexity by Christos Papadimitriou.
• Introduction to the theory of computation by Michael Sipser.

Requirements:

There will be an exam at the end of the course. During the lectures I will sometimes present questions and challenges for you to think about. You are encouraged to work on these questions.

Exercises:

These exercises are not for submission. However you are strongly encouraged to solve them.

- Exercise 1 (on space complexity)

- Exercise 2 (on diagonalization and the polynomial time hierarchy)

- Exercise 3 (on circuits and randomized algorithms)

- An example of a take home exam (from several years ago). Solving this is a good way to make sure you know the material.

- Examples of class exams: (1) (2) (3) (4)

Material:

• Space complexity. The material can be found in Part I chapter 4 in Arora-Barak, or Chapter 5 in Goldreich. Most of this material is also available in Sipser's and Papadimitriou's books.
• Definition of TMs that run in space << n.
• Example: Addition in space O(log n).
• Composition of functions that are computable in logspace.
• 3-SAT in linear space.
• Definition of L, NL, PSPACE, NPSPACE.
• Example: directed connectivity in NL.
• A randomized algorithm for undirected connectivity in logspace (no proof yet)
• NSPACE(s(n)) in TIME(2^{O(s(n))}) (configuration graphs). (corollary: NL in P).
• Savich's theroem: directed connectivity in space log^2 n.
• Corollary: NSPACE(s(n)) in SPACE(s(n)^2). (implies: NPSPACE=PSPACE).
• Definition of quantified Boolean formula and the language TQBF.
• TQBF is PSPACE complete.

• NL completeness.
• dPATH is NL complete.
• Definition of NL by certificate verification.
• NL=co-NL.
• 2-SAT in NL (sketch only).

• Diagonalization.
• Time complexity, quick review.
• Deterministic time hierarchy theorem.

o The generality of the argument: the deterministic space hierarchy theorem.

o Why the argument doesn't give a nondeterministic time hierarchy theorem.

o The non-deterministic time hierarchy theorem (delayed diagonalization).

o Weakness of diagnolization: results proven this way hold for any oracle.

o An oracle A such that NP^A <> P^A. Implies impossibility of proving NP<>P by direct diagonalization.

o The notion of relativizing statements and proofs.

o The statement NP=P and NP<>P are non-relativizing.

· The polynomial time hierarchy

o Definition with quantifiers and definition with oracles (equivalence is an exercise).

o The hierarchy collapses if PH has a complete problem.

o The hierarchy collapses if Sigma_i = Pi_i.

o Padding arguments.

o Time space tradeoffs: NTIME(n) not contained in TISP(n^{1.2},n^{0.2}).