Section outline

  • ΔΕΥΤΕΡΑ

    • Interactive Proofs: Shamir's Theorem (IP=PSPACE)

     

    ΠΕΜΠΤΗ

    • Counting Complexity: Counting vs Decision Problems, the class #P, #SAT, PERMANENT, Parsimonious, Cook and Cook[1] (metric) reductions for Counting Problems, Valiant-Vazirani Theorem

    Προτεινόμενη Μελέτη:

    • Ch 8: Section 8.3 από το [2]
    • Chapter 18 από το [1].