CSE 540 Topics (Fall 2017)
This is a tentative list of topics for this semester, in roughly the
order that I expect to treat them. Exactly how many of these topics
are covered, and the depth in which they are covered, is going to
depend on how things go, so expect some changes. I envision some chance
that some of the last few topics in the list below will have to be dropped.
- Turing Machines, variants (Ch. 3)
- Decidability (4.1)
- Undecidability (4.2)
- Reducibility (5.1, 5.3)
- Rice's Theorem (Ex. 5.28)
- Recursion Theorem (6.1)
- Decidability of Logical Theories (6.2, 6.3)
- Recursive Functions (not in Sipser)
- Time Complexity (7.1)
- Complexity Class P (7.2)
- Complexity Class NP (7.3)
- NP-Completeness, Cook-Levin Theorem (7.4)
- Additional NP-complete Problems (7.5)
- Space Complexity, Savitch's Theorem (8.1)
- Alternating Turing Machines (10.3)
- PSPACE, PSPACE-Completeness (8.2, 8.3)
- Complexity Classes L and NL (8.4, 8.5)
- NL = co-NL, Immerman-Szelepcsenyi Theorem (8.6)
- Hierarchy Theorems (9.1, skip EXPSPACE-completeness)
- Relativization (9.2)
- Circuit Complexity (9.3)
- Probabilistic Algorithms, BPP, RP (10.2)
- Interactive Proof Systems, IP=PSPACE (10.4)