Computational Complexity (Fall 2010-2011)

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.

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.te 8/6/2009.

Lectures:

 

 

        Lecture 3: Space complexity (continued)

o   NL=coNL

o   2-SAT in coNL.

o   The language TQBF and its relation to 2-player games.

o   TQBF in PSPACE

 

        Lecture 4: Space complexity (continued)

o   TQBF is complete for PSPACE

        Diagonalization

o   The deterministic time hierarchy theorem.

o   Space hierarchy theorem and why doesn't the proof extend for nondeterministic time.

 

        Lecture 5: Diagonalization (continued)

o   The nondeterministic time hierarchy theorem (delayed derandomization).

o   Oracles.

o   Relativization. A proof for P=NP or P<>NP cannot relativize.

 

        Lecture 6:

o   Oracle construction for relativized world with P<>NP.

o   The polynomial time hierarchy (Chapter 5 in Arora-Barak).

o   Definition with quantifiers and definition with oracles.

o   The hierarchy collapses if PH has a complete problem.

o   The hierarchy collapses if Sigma_i = Pi_i.

 

        Lecture 7: Time-space tradeoffs (Chapter 5 in Arora-Barak).

o   Padding arguments.

o   3-SAT not in TISP(n^{1.1},n^{0.1})

 

        Lecture 8: Boolean circuits (Chapter 6 in Arora-Barak).

o   Circuits and circuit families.

o   Circuit families compute undecidable functions.

o   Uniform circuits and equivalence with P.

o   Non-uniform TMs. The class P/poly and equivalence with polynomial size circuit families.

o   The Karo-Lipton theorem: NP in {.poly implies PH collapses.

 

        Lecture 9: Low depth circuits.

o   The classes AC^i,NC^i and their relationship with parallel computing.

o   Parity not in AC0. Proof by Razborov-Smolensky (see Arora-Barak chapter 14).