[Computational Complexity] The Graduate Complexity Course

Expand Messages
• 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
Message 1 of 1 , Nov 30 7:20 AM
• 0 Attachment
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

Your message has been successfully submitted and would be delivered to recipients shortly.