Section outline

  • ΔΕΥΤΕΡΑ

    • Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL & Undirected REACHABILITY.



    ΠΕΜΠΤΗ

    • Different types of reductions (logspace, Karp, Cook), Circuits, P-completeness. NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.


    Μπορείτε να διαβάσετε:
    -Ch.8 from [1]