[Computational Complexity] The Graduate Complexity Course
After my post on teaching PCPs, a reader questioned the wisdom of spending 6-8 lectures on PCP and asked what topics should be taught in an introductory graduate complexity course. This is not a new issue. In the spring of 1985 I took a graduate complexity course with Juris Hartmanis at Cornell and in the spring of 1986 took a graduate complexity course with Michael Sipser at Berkeley with only the polynomial-time hierarchy in the intersection of the two courses.
Here is my list of the topics and theorems that should be covered in a graduate complexity course. Depending on the school, some of this material is covered in undergraduate courses. More material should be added based on the interests of the instructor.
- DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ ∪cDTIME(cf(n)).
- Basic time and space hierarchies.
- NSPACE(s(n))⊆DSPACE(s2(n)) and NSPACE(s(n)) = co-NSPACE(s(n)).
- The P versus NP problem and NP-completeness. SAT is NP-complete.
- The polynomial-time hierarchy.
- Alternation (Alternating polynomial-time = PSPACE).
- Probabilistic Complexity Classes (BPP, RP, ZPP). BPP ⊆ PH.
- Counting (PH ⊆ P#P).
- The PCP theorem. Even if you don't do the proof, state the theorem and the implications for hardness of approximation.
Posted by Lance to Computational Complexity at 11/30/2005 09:12:00 AM