Week 2: UNDECIDABILITY I: Decidable languages from language theory; Halting problem and undecidability; additional undecidable problems; reducibility and mapping reductions;
Week 3: UNDECIDABILITY II: More undecidability; Rice's Theorem; Turing nonrecognizability; computation histories; undecidability of ALL_CFG and COMMON_CFG; Implications of undecidability;
Week 4: INTRO TO COMPLEXITY: Intro to complexity theory; Time complexity; relationship between variants (multitape/nondeterministic); complexity classes; Clases P and NP; examples of problems in P and NP.;
Week 5: NP COMPLETENESS I: The P versus NP question; polynomial-time mapping reductions; Satisfiability; NP-completeness; Statement of Cook-Levin theorem; Examples of polytime mapping reduction (3SAT to CLIQUE); circuit complexity; CIRCUIT SAT is NP-complete; Proof of Cook-Levin theorem
Week 6: NP COMPLETENESS II: Examples of NP-complete reductions and the ubiquity of NP-completeness;
Week 7: SPACE COMPLEXITY: Space complexity; Time versus Space; Savitch's theorem; the classes PSPACE, L, and NL; Example problems in L and PSPACE; PSPACE-completeness of TQBF; ubiquity of PSPACE-completeness;
Week 8: PROBABILISTIC AND INTERACTIVE COMPUTATION: Formal definitions and kinds of algorithms; Improving success probabilities; relation to circuit complexity; Interactive Proofs; Introduction to Complexity-theory in Cryptography;
Week 9: NO CLASS: Thanksgiving eve;
Week 10: PROBABILISTICALLY CHECKABLE PROOFS: Definition and PCP Theorem; Implications for approximation problems;.
Week 11: FINISH OUTSTANDING TOPICS and REVIEW
Final Exam