CSEP 590TU Complexity Theory, Autumn '03 Course Outline

Week 1: INTRO TO COMPUTABILITY: Introduction; History of Computability; Turing machines; decidablility and recognizability; examples; universal Turing machine; Turing machine variants; Church-Turing thesis and robustness of Turing machine models. 

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


Final Exam