Complexity theory, Spring 2002
Lecture log
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
thesis. Notes

More on R and RE (and coRE). An example of an undecidable language. Encoding
a TM as a string. Nondeterministic TMs. Notes.

Recursive manytoone reductions, REcompleteness, coRE. Universal TM.
Halting language and Halting on empty string. The speedup 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,tpath in a directed graph. Notes.

More about the graph reachability problem. Savitch's theorem. The class
coNL. Started on NL=coNL. Why is it nontrivial to solve nonreachability
in NL? Notes

NLalgorithm for graph nonreachability. Definitions of "closed under reductions"
and "complete problems". Logspace reductions and polytime reductions. Example:
reduction of CLIQUE to SAT. Notes

NPcertificates and polynomially balanced relations. Circuit value is Pcomplete,
Circuit satisfiability and 3SAT are NPcomplete. Notes

coNP. Primality in (NP intersect coNP). Proof that Z_{p}^{*}
is cyclic. Chineese remainder theorem. Notes

TMs with oracles. Finding the largest clique using a CLIQUEoracle. FNP.
Some PSAPCEproblems (Generalized Geography, QSAT). Notes

Proof that QSAT is PSPACEcomplete. Probabilistic TMs. The
MillerRabin 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 NPOproblems. Examples: deterministic approxiation
of MAX3SAT, polynomial time approximation scheme for KNAPSACK. Quick
overview of some lower bounds. Approximation preserving reductions:
Lreductions. Notes

An overview of some connections between cryptography and complexity
illustrated by notions of security, pseudo random generators, oneway functions, bit
commitment, and zeroknowledge proofs.
Notes

Interactive proofs and the class IP. Examples: graph nonisomorphism,
permanent of 0/1matrices. Proof that
#P is a subset of IP, and mentioned IP = PSPACE.
Notes

Parallel complexity classes and computation models. Overvies of PRAM
and examples of PRAMalgorithms for matrix product, reachability and
summing elements of a list. The circuit classes NC_{k} and
AC_{k}. Notes