Section outline

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

    • The Structure of NP: Proof of Ladner’s Theorem, Padding, Density, Sparse Sets, Mahaney's Theorem.


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

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


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