Computational Complexity Theory, Fall 2006
Computational complexity theory is a scientific discipline
aiming at answering or at least getting a better understanding
of questions such as the following by giving them precise
The purpose of the course is to give an introduction to the
field and its most important techniques.
- Are mathematical proofs easy to find?
- Can the use of randomness speed up some computation substantially?
- Can massive parallelism speed up all non-trivial
Contents: (Details may vary)
Space bounded computation, crossing sequence arguments,
Savitch' theorem. Immerman-Szelepcsenyi Theorem, NL-completeness,
hierarchy theorems, P and EXP, padding, circuits and non-uniformity, P
vs. P/poly, P-completeness, Paul-Pippenger-Valiant theorem,
alternation, games, PSPACE-completeness, relativized computation and
oracles, massive parallelism, P vs. NC, the fine structure of P,
randomized computation, BPP, RP, pBPP and pRP, pBPP=pRP[pRP],
dispersers and extractors, Trevisan's extractor, pseudorandom
generators and hitting set generators, Sipser's generator, interactive
proofs, IP=PSPACE, the PCP-theorem, hardness of approximations,
towards P vs. NP (diagonalization approach), time-space tradeoff for
SAT, towards P vs. NP (combinatorics approach), bounded depth
computation, towards independence of P vs. NP, natural proofs. SL=L.
The course spans the Fall semester of 2006. The exam is oral.
The course is graded (using the 00-13 scale).
To take the exam (and gain 10 ECTS), five compulsory assignments
must be solved in a satisfactory way during the course.
In addition to a problem set, the compulsory assignments will consist
of the production of lecture notes. These, together with lecture notes
on the Internet will define the curriculum of the course.
The exam dates are January 12th and January 26th. The exam
is a conversation with the notes of the student as the point
Please note that the student notes below are unedited. You should read
each others notes with a critical mindset and are encouraged to
provide feeedback to each other (and to me).
- August 30 Introduction to the course. What is computational
For the first lecture, you might want to read Oded Goldreich's "Things
that should have been taught in previous courses".
Scribe: Thomas Mølhave. Notes.
- September 1st Deterministic Turing machine model. DTIME and
DSPACE. Graph accesibility problem (GAP) is in DSPACE[O(log^2 n)].
Time hierarchy theorem. For this lecture, Oded Goldreich's note is good
background reading (In fact all of Oded's notes in
this directory are excellent
and we will cover most of the material in some order, so you might as
print out all these notes as a main text for this course! We
shall also be using Eric
Allender's notes, so why not also take a look at those.
Scribe: Johnni Winther. Notes (notes
updated October 23)
- September 6th Biimmunity (exercise). Space hierarchy
theorem. Non-uniform complexity. PSIZE = P/poly. EXPSPACE is not a
subset of P/poly. Nondeterministic Turing machines. Logspace
reductions. Scribe: Miroslava Sotakova. Notes.
- September 8th Logspace reductions are closed under
composition. Downward closure of complexity classes under reduction.
Hardness and Completeness. Savitch' theorem: NSPACE[s] is in
DSPACE[O(s^2)]. Upwards translation/padding. coNP vs. NP. For this
lecture and the last, Oded's note number 5
is good reading. Scribe: Morten Kuhnrich. Notes.
Notes revised December 12th.
- September 13th Bimmunity revisited. Downward closure
revisited. Immerman-Szelepscenyi theorem: NSPACE[O(s)]=coNSPACE[O(s)].
Hierarchy theorems for nondeterministic computation, indirect
Oded's note number 6.
Scribe: Martin Mortensen. Notes
- September 15th Complete problems for P, EXP and NEXP. Succinct
Nondeterminism as OR-parallelism. More general massive
parallel computation: Alternating Turing machines as a model capturing
self-reproducing computers. Alternating Turing machines as a formalism
for describing two-player games. ATIME. ASPACE. Scribe: Lea Troels
Møller Pedersen. Notes.
- September 20th
Garden of Eden game. AL = P. AP =
PSPACE. FORMULA VALUE PROBLEM in L. Scribe: Morten Kuhnrich.
Notes. Notes updated Jan 1st.
- September 22th
Quantified Boolean formulas. QBF is PSPACE complete.
Fortnow's theorem: SAT is not in the intersection of NL and
SIZE[n polylog n].
Paper. Scribe: Thomas Mølhave. Notes.
- September 27th
Generalized Geography is complete for PSPACE. Cook reductions.
Oracle machines. The polynomial hierarchy.
Read Oded's note
Scribe: Miroslava Sotakova. Notes.
- September 29th
hierarchy doesn't collapse" as a scientific hypothesis. Karp-Lipton
theorem. Relativizable proof technqiues. Scribe: Morten Dahl.
- October 4th
A non-relativizable proof. Meyer's theorem. Randomized computation.
Slides. Scribe: Peter Sebastian Nordholt: Notes.
- October 6th Valiant-Vazirani theorem. Promise problems.
prBPP. A complete problem for prBPP. Scribe: Johnni Winther.
Notes. Corrections to notes added
- October 11th Equivalence of prBPP = prP and derandomizing
Monte Carlo integration. prBPP= prRP[prRP]. Scribe: Henrik Hald
Notes. Notes updated November 22th.
- October 13th Alternating Turing machines with random
access to input. Uniform circuits. NCi, ACi.
NC1 in L, NL in AC1. Circuits
with oracle gates. Constant depth reductions. Complete problems
for L. TC0. Scribe: Henrik Hald Nørgaard.
We shall readjourn on November 15th, where you should hand
in solutions to this homework.
- November 15th Addition in AC0 and Multiplication
complete for TC0. TC0 is in NC1.
Statement of Hastad Switching Lemma and its implication for
showing that PARITY is not in AC0. Scribe: Daniel Andersson.
- November 17th Proof of the switching lemma. Smolensky's
polynomial method. Scribe: Martin Mortensen.
Notes revised December 13th.
- November 22th Rest of Smolensky's polynomial method.
Razborov-Rudich natural proofs. Interactive proofs. IP=PSPACE.
Scribe: Henrik Hald Nørgaard. Notes
- November 24th IP=PSPACE. AM and MA. Scribe: Daniel
- November 29th PCP theorem. Notes. Scribe: Morten Dahl. Notes.
- December 1st More PCP. Scribe: Johnni Winther. Notes.
- December 6th PCP's and gap creating
reductions. Derandomization. Dispersers. Scribe: Lea Troels Møller
Pedersen. Background reading
(Section on Dispersers and Extractors). Notes: Notes. Slides (for this and coming lectures).
- December 8th Derandomization. Extractors. Hitting set
- December 13th Hitting set generator based on time vs. space
assumption. Miltersen-Vinodchandran hitting set generator.
(Sections on hitting set generators). Notes.
- December 15th Discussion of homeworks. Comments, complaints.