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

Week 11: FINISH OUTSTANDING TOPICS and REVIEW

Final Exam