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.