Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] The Graduate Complexity Course

Expand Messages
  • Lance
    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
    • 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.