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, Parallel computation (classes NC, RNC, AC, TC).


    Μπορείτε να διαβάσετε:
    -Sections 7.4, 7.5 from [2]
    - Sections 6.1 - 6.7 from [2]