# Computational Complexity (Spring 2009)

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.

Exercises:

Exercise are given so that you can make sure that you understand the material. Submitting the exercises is not mandatory. I will check a small sample of the questions in each exercise and will give grades. The exercise grade will be 10% of the final grade. (The exercise grade will not be used if it reduces the final grade.

Lectures:

• Lecture 1:
• High level description of the course's objectives and the achievements of complexity theory.
• Reminder of time complexity and the classes P,NP.
• Space complexity: (basics). 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.
• 3-SAT in linear space.
• Definition of TMs that run in space << n.
• Example: Addition in space O(log n).
• Definition of L, NL, PSPACE, NPSPACE.
• Example: directed connectivity in NL.
• NSPACE(s(n)) in TIME(2^{O(s(n))}) (configuration graphs). (corollary: NL in P).
• Savich's theroem: NSPACE(s(n)) in SPACE(s(n)^2). (corollary NPSPACE=PSPACE).
• Directed and undirected connectivity in nondeterministic space O(log n).
• A randomized algorithm for undirected connectivity in logspace (no proof yet).

• Lecture 2:
• Space complexity: The class NL (Part I chapter 4 in Arora-Barak).
• Definition of NL using logarithmic space verifiers and certificates.
• directed connectivity in NL (proof using certificates).
• Composition of functions that are computable in logspace.
• Logspace reductions. Definition, the notion of NL completeness and comparison to poly-time reductions.
• Directed connectivity is complete for NL.
• NL=co-NL: We showed this by showing that the complement of directed connectivity is in NL.

• Lecture 3:
• Space complexity: The class NL (continued). The material can be found in Part I chapter 4 in Arora-Barak.
• The problem 2-SAT.
• 2-SAT in P.
• 2-SAT in NL.
• 2-SAT is NL complete.
• Space complexity: The class PSPACE.
• Quantified formulae and the problem TQBF.
• TQBF in PSPACE.
• PSPACE completeness.
• TQBF is complete for PSPACE.
• Interpretation of TQBF as a 2-player game.

• Lecture 4:
• Diagonalization. The material can be found in Part I chapter 3 in Arora-Barak.
• The idea of diagonzlization.
• The deterministic time hierarchy theorem.
• The deterministic time hierarchy theorem. (Corollary P <> EXP).
• The space time hierarchy theorem. (Corollary L<>PSPACE).
• The nondeterministic time hierarchy theorem. (Delayed Diagonaliztion).

• Lecture 5:
• Diagonalization (continued)
• Oracles and relativization. (Definitions and examples).
•  The statement P=NP does not relativize. (Part I chapter 3 in Arora-Barak).
• Philosophical discussion of the meaning of relativization.
• The polynomial time Hierarchy. The material can be found in Part I chapter 5 in Arora-Barak.
• Definition of the polynomial time hierarchy.
• The hierarchy collapse if Pi_i=Sigma_i or if PH has a complete problem.
• SAT not in TISP(n^{1.2},n^{0.2}) (statement only, proof next week).

• Lecture 6:
• SAT not in TISP(n^{1.2},n^{0.2})
• Boolean circuits (Chapter 6 in Arora-Barak).
• Circuits and circuit families.
• Uniform circuits.
• Nonuniform Turing machines and P/poly.
• The Karp-Lipton theorem: NP in P/poly implies PH collapses.
• Definition of AC0 and NC.
• Relation to parallel computation.

• Lecture 7: Circuit lower bounds.
• Parity not in AC0 (proof using the Razborov-Smolensky method of approximations see chapter 15 in Arora-Barak).

• Lecture 8: Probabilistic computation (chapter 8 in Arora-Barak)
• Review of probability theory.
• The Chernoff inequality and sampling.
• Randomized quicksort.
• Polynomial identity testing and Schwartz-Zippel.
• Finding a perfect matching in randomized NC.
• Definition of randomized algorithms.
• The classes BPP and RP.
• Error reduction for randomized algorithms (statement only).