# 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.

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.