SYLLABUS for CMSC 858- COMPUTATIONAL COMPLEXITY

COURSE WEBSITE: www.cs.umd.edu/ gasarch/858/858.html

(there is a tilde before the ``g'' in ``gasarch'')

OBJECTIVES: We try to determine why certain problems are hard by defining classes to put them in.

WHEN/WHERE: MWF 1-2, CSI 2118.

TEXT: Notes and handouts will be handed out.

OFFICE HOURS: MW 2-3. Or by apointment. I am around most days of the week. Feel free to email me at gasarch@cs.umd.edu or call at (301) 405-2698.

PREREQUISITE: The prerequisite is CMSC 451 or CMSC 452 or permission of the instructor.

GRADING: One Midterm, March 29 at night. One Final, Friday May 14, 1:30. Approx 10 HWs. HW is 30% of the grade MIDTERM is 30% of the grade Final is 40% of the grade

CONTENT:

1. How can some problems be more undecidable than others? Computability and reductions. (1 week)

2. Are there problems that take LOTS of time to decide? Time-hierarchy theorems. (1 week)

3. Why do we think SAT and many other problems are hard? Cook's theorem and reductions. (1 week)

4. Why do we think that techniques from recursion theory are not going to suffice to solve P vs NP and other problems? (1 week)

5. Do we actually know anything? Savitch's theorem, Alternation time is PSPACE, and the Immerman-Szelepcsenyi Theorem. (2 week)

6. Why do we thing Sparse sets are NO NP-Complete? Mahaney's theorem, Karp-Lipton theorem, and the Poly Hierarchy. (1 week)

7. Why do we think Graph Isompophism is NOT NP-complete? Interactive Proof Systems. (2 weeks)

8. Why do we think Clique and many other problems are hard to approximate? The PCP theorem (2 weeks)

9. Why do we think $P=BPP$? The Nisan-Wigderson paper and its sequels. (2 weeks)

10. Why do we think COUNTING-SAT is much harder than SAT? Sharp-P and Toda's Theorem. (2 weeks)