Lecture 1: Introduction; Turing machines; decidablility and
           recognizability; examples; enumerators 
<p> 
Lecture 2: Closure of decidable languages; Turing machine variants;
           Church-Turing thesis and robustness of Turing machine
           models.&nbsp;</p>
<p>
Lecture 3: Decidable languages from language theory; Halting problem
           and undecidability; reducibility (HALT_TM)&nbsp;</p>
<p>
Lecture 4: More undecidability (eg. ALL_TM); mapping reduction; Rice's
           theorem; Turing nonrecognizability&nbsp;</p>
<p>
Lecture 5: Computation histories; undecidability of ALL_CFG and COMMON_CFG;
           the Post Correspondence problem</p>
<p>&nbsp;Lecture 6: Finish proof of PCP undecidability; Intro to complexity
           theory; Time complexity; relationship between variants (multitape/nondeterministic)</p>
<p>Lecture 7: The class P; Examples of problems in P (PATH, every CFL,
           RELPRIME); The class NP&nbsp;</p>
<p>
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)&nbsp;</p>
<p>
Lecture 9: Circuit complexity; CIRCUIT SAT is NP-complete; Proof of
           Cook-Levin theorem&nbsp;</p>
<p>
Lecture 10: Finish reduction from CIRCUIT SAT to 3SAT; Examples of
           NP-complete problems (HAMPATH; SUBSET SUM)&nbsp;</p>
<p>

Lecture 11: Space complexity; Savitch's theorem; the class PSPACE;
            Examples in PSPACE&nbsp; (SAT, ALL_NFA)&nbsp;</p>
<p>
Lecture 12: PSPACE-completeness of TQBF; Relation to two person games;
            PSPACE-completeness of generalized geography.&nbsp;</p>
<p> 
Lecture 13: Sublinear space computation; the classes L and NL;
            Examples in L and NL; logspace transducers and reductions;
            NL-completeness of PATH.&nbsp;</p>
<p> 
Lecture 14: NL= coNL; Introduction to provable intractability and
            hierarchy theorems.&nbsp;</p>
<p> 

Lecture 15: Space hierarchy theorem; Statement of time hierarchy
            theorem; Intractability of EQ_{REX-exponentiation};
            Relativization&nbsp;</p>
<p> 
Lecture 16: Oracle separating P and NP; Intro to probabilistic
            computation; definition of classes BPP, RP, coRP.&nbsp;</p>
<p>
Lecture 17: Amplification of error probability for RP, BPP; Polynomial
            identity testing; equivalence of read-once branching
            programs.</p>
<p>&nbsp;Lecture 18: BPP is in Sigma_2; Intro to Interactive Proofs; The graph
            nonisomorphism interactive protocol</p>
<p>&nbsp;Lecture 19: #SAT is in IP; Extension to IP protocol for TQBF (sketch
            of idea)&nbsp;</p>
<p>
Lecture 20: Advanced topic: hardness of approximation and very
            efficient probabilistic checking of NP proofs.</p>