Section outline

  • ΔΕΥΤΕΡΑ

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

    ΠΕΜΠΤΗ

    • Reductions & Completeness: Different types of reductions (logspace, Karp, Cook), Circuits,
      P-completeness.