Browse Groups

• ## [Computational Complexity] The Graduate Complexity Course

(1)
• NextPrevious
• 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, 2005
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.