Complexity theory, Spring 2002
My lecture notes are available as pdf files thanks to Mattias Amnefelt.
Take them for what they are: notes I prepared for myself. Beware of errors
and omissions as well as my handwriting.
Introduction: Solving computational problems using bounded resources. Administration.
Turing machines: definition and examples (palindromes). Definitions of
computability, decidability and recursive enumerability. The classes R
(recursive languages) and RE (recursively enumerable languages). Church's
More on R and RE (and coRE). An example of an undecidable language. Encoding
a TM as a string. Nondeterministic TMs. Notes.
Recursive many-to-one reductions, RE-completeness, coRE. Universal TM.
Halting language and Halting on empty string. The speed-up theorem. Definition
of complexity classes: L, NL, P, NP, PSPACE, NPSPACE. Notes.
Inclusions between classes (L, NL, P, NP, PSPACE, and EXP). Time and space
hierarchies (halting in bounded time). NTIME vs SPACE, NSPACE vs TIME.
Connection between SPACE and finding an s,t-path in a directed graph. Notes.
More about the graph reachability problem. Savitch's theorem. The class
coNL. Started on NL=coNL. Why is it non-trivial to solve non-reachability
in NL? Notes
NL-algorithm for graph non-reachability. Definitions of "closed under reductions"
and "complete problems". Logspace reductions and polytime reductions. Example:
reduction of CLIQUE to SAT. Notes
NP-certificates and polynomially balanced relations. Circuit value is P-complete,
Circuit satisfiability and 3SAT are NP-complete. Notes
coNP. Primality in (NP intersect coNP). Proof that Zp*
is cyclic. Chineese remainder theorem. Notes
TMs with oracles. Finding the largest clique using a CLIQUE-oracle. FNP.
Some PSAPCE-problems (Generalized Geography, QSAT). Notes
Proof that QSAT is PSPACE-complete. Probabilistic TMs. The
Miller-Rabin primality test analyzed. The class RP. Notes
The classes RP, coRP, BPP, ZPP and their relations. Probabilistic test of multilinear
polynomial (checking existence of bipartite matching). ZPP nd expected
polynomial time. Notes
Approximability of NPO-problems. Examples: deterministic approxiation
of MAX3SAT, polynomial time approximation scheme for KNAPSACK. Quick
overview of some lower bounds. Approximation preserving reductions:
An overview of some connections between cryptography and complexity
illustrated by notions of security, pseudo random generators, one-way functions, bit
commitment, and zero-knowledge proofs.
Interactive proofs and the class IP. Examples: graph non-isomorphism,
permanent of 0/1-matrices. Proof that
#P is a subset of IP, and mentioned IP = PSPACE.
Parallel complexity classes and computation models. Overvies of PRAM
and examples of PRAM-algorithms for matrix product, reachability and
summing elements of a list. The circuit classes NCk and