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.

Resources for exam:

Some exercises on the material:

· Ex1

· Ex2

· Ex3

A home exam that was given
several years ago.

Past class exams:

· Moed a

· Moed b

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

- Lecture
2: Space complexity (continued): The material can be found in Part I chapter 4 in Arora-Barak,
or Chapter 5 in Goldreich.
- NL
completeness.
- dPATH is NL complete.
- Definition
of NL by certificate verification.
- NL=co-NL.
- 2-SAT
in NL (sketch only).
- Definition
of quantified Boolean formula and the language TQBF.

- Lecture
3: Space complexity (continued) and review of time complexity.
- TQBF
is PSPACE complete.
- Time
complexity, quick review.
- Deterministic
time hierarchy theorem.

·
Lecture 4: Diagonalization

o Another
look at the proof of the 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.

·
Lecture 5: Diagonalization (Continued)

o The
notion of relativizing statements and proofs.

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

o The
polynomial time hierarchy. See nect lecture

·
Lecture 6: 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}). (Chapter
5 in Arora-Barak).

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

o Circuits
as hardware.

o Circuits
as non-uniform Turing machines (the notion of P/poly and equivalence of
definitions).

o Uniform
circuits and alternative definition of P.

o Counting
argument: The existence of functions not computable by size O(2^n/n)
circuits.

o The
Karp-Lipton theorem: (NP in P/poly implies PH=Sigma_2).

o Kannan's lower bound: For every constant c
there is a language in Sigma_2 which cannot be computed by circuits of size (n^c).

·
Lecture 8: Lower bounds
for AC0.

o The
notions of AC_i and NC_i
and relation to parallel computing.

o The
proof of Razborov and Smolensky
that Parity is not in AC0. (see Arora-Barak chapter 14).

·
Lecture 9: Probabilistic
Computation.

o The
notion of a randomized algorithm with one-sided or two sided error.

o The
classes BPP, RP, co-RP.

o Examples
of randomized algorithms (dPATH in Randomized Logspace, Primality testing and
identity testing in BPP).

o Error
reduction for randomized algorithms (for both RP and BPP).

·
Lecture 10: Probabilistic
Computation (continued).

o BPP
in P/poly.

o BPP
in Sigma_2.

o The
notion of interactive proofs. Definition of the classes AM and IP.

o co-GI is in AM.