Section outline

  • Δευτέρα 30 Οκτωβρίου

    • The Structure of NP: Mahaney's Theorem.

    • The Structure of NP: Enumerations, Ladner’s Theorem, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.


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

    • Randomized Computation: 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]