Section outline

  • ΔΕΥΤΕΡΑ

    • P-completeness, NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.



    ΠΕΜΠΤΗ

    • Oracles & The Polynomial Hierarchy: Oracles and oracle classes. Oracle worlds.


    Reading:
    -Section 14.3, Ch.17 from [1]