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

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

  4.  
  5. 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.

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

  8.  
  9. 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

  10.  
  11. 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

  12.  
  13. NP-certificates and polynomially balanced relations. Circuit value is P-complete, Circuit satisfiability and 3SAT are NP-complete. Notes

  14.  
  15. coNP. Primality in (NP intersect coNP). Proof that Zp* is cyclic. Chineese remainder theorem.  Notes

  16.  
  17. TMs with oracles. Finding the largest clique using a CLIQUE-oracle. FNP. Some PSAPCE-problems (Generalized Geography, QSAT).  Notes

  18.  
  19. Proof that QSAT is PSPACE-complete. Probabilistic TMs. The Miller-Rabin primality test analyzed. The class RP.  Notes

  20.  
  21. 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

  22.  
  23. Approximability of NPO-problems. Examples: deterministic approxiation of MAX3SAT, polynomial time approximation scheme for KNAPSACK. Quick overview of some lower bounds. Approximation preserving reductions: L-reductions.  Notes

  24.  
  25. 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.   Notes

  26.  
  27. 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.   Notes

  28.  
  29. 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 ACk.   Notes