Section outline

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

    • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FPNP.
    • The Structure of NP: Enumerations, Ladner’s Theorem, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.


    Πέμπτη 26 Οκτωβρίου

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

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