Section outline

  • ΔΕΥΤΕΡΑ

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



    ΠΕΜΠΤΗ

    • Different types of reductions (logspace, Karp, Cook), Circuits.


    Reading:
    -Ch.8 from [1]