Lecture 2: Closure of decidable languages; Turing machine variants; Church-Turing thesis and robustness of Turing machine models.

Lecture 3: Decidable languages from language theory; Halting problem and undecidability; reducibility (HALT_TM)

Lecture 4: More undecidability (eg. ALL_TM); mapping reduction; Rice's theorem; Turing nonrecognizability

Lecture 5: Computation histories; undecidability of ALL_CFG and COMMON_CFG; the Post Correspondence problem

Lecture 6: Finish proof of PCP undecidability; Intro to complexity theory; Time complexity; relationship between variants (multitape/nondeterministic)

Lecture 7: The class P; Examples of problems in P (PATH, every CFL, RELPRIME); The class NP

Lecture 8: Examples in NP; the P vs NP question; Satisfiability; NP-completeness; Statement of Cook-Levin theorem; Example of polytime mapping reduction (3SAT to CLIQUE)

Lecture 9: Circuit complexity; CIRCUIT SAT is NP-complete; Proof of Cook-Levin theorem

Lecture 10: Finish reduction from CIRCUIT SAT to 3SAT; Examples of NP-complete problems (HAMPATH; SUBSET SUM)

Lecture 11: Space complexity; Savitch's theorem; the class PSPACE; Examples in PSPACE (SAT, ALL_NFA)

Lecture 12: PSPACE-completeness of TQBF; Relation to two person games; PSPACE-completeness of generalized geography.

Lecture 13: Sublinear space computation; the classes L and NL; Examples in L and NL; logspace transducers and reductions; NL-completeness of PATH.

Lecture 14: NL= coNL; Introduction to provable intractability and hierarchy theorems.

Lecture 15: Space hierarchy theorem; Statement of time hierarchy theorem; Intractability of EQ_{REX-exponentiation}; Relativization

Lecture 16: Oracle separating P and NP; Intro to probabilistic computation; definition of classes BPP, RP, coRP.

Lecture 17: Amplification of error probability for RP, BPP; Polynomial identity testing; equivalence of read-once branching programs.

Lecture 18: BPP is in Sigma_2; Intro to Interactive Proofs; The graph nonisomorphism interactive protocol

Lecture 19: #SAT is in IP; Extension to IP protocol for TQBF (sketch of idea)

Lecture 20: Advanced topic: hardness of approximation and very efficient probabilistic checking of NP proofs.