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

Lectures:

- Lecture 1: Introduction
and space complexity.
- 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.
- A
randomized algorithm for undirected connectivity in logspace
(no proof yet)

- Lecture 2: Space
complexity (continued).
- The
material can be found in Part I chapter 4 in Arora-Barak,
or Chapter 5 in Goldreich.
- 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).
- 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.
- Definition
of NL using logarithmic space verifiers and certificates.

·
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).