Section outline

  •  Week 3

    • Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics, Savitch’s Theorem, Immerman-Szelepscényi Theorem.
    • Basic notions and results of Complexity Theory: NL-completeness, P-completeness, The Cook-Levin Theorem, NP-completeness, PSPACE-completeness, Logical Characterizations & Descriptive complexity.