Section outline

  • Δευτέρα

    • The Structure of NP: Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets, Mahaney's Theorem.
    • Randomized Computation: Probabilistic Turing machines, the class BPP.

    Πέμπτη

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



    Μπορείτε να διαβάσετε:
    • Section 14.2 from [1]
    • Sections 7.1-7.5 from [2]