Section outline

  • ΔΕΥΤΕΡΑ

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


    ΠΕΜΠΤΗ

    • The Structure of NP: density, sparse sets, Mahaney's Theorem

    Reading:
    -Sections 14.1, 14.2 from [1]