Section outline

  • ΔΕΥΤΕΡΑ

    • Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs

     

    ΠΕΜΠΤΗ

    • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, Public and private coins, Arthur-Merlin Games

     

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

    • Ch 6: Sections 6.1-6.5 από το [2]