Section outline

  • ΔΕΥΤΕΡΑ

    • Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.



    ΠΕΜΠΤΗ

    • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice.


    Reading:
    -Sections 7.4, 7.5 from [2]
    -Sections 6.1-6.6 from [2]