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)) ⊆ ∪
_{c}DTIME(c^{f(n)}). - Basic time and space hierarchies.
- NSPACE(s(n))⊆DSPACE(s
^{2}(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- DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆
NSPACE(f(n)) ⊆ ∪