Section outline

  • Δευτέρα 6 Νοεμβρίου

    • Randomized Computation: Semantic and syntactic classes, the “P vs BPP” question, Relativized Results.


    Πέμπτη 9 Νοεμβρίου

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


    Μπορείτε να διαβάσετε:

    • Sections 7.1-7.5 from [2]
    • Sections 6.1-6.7 from [2]