Section outline

  • ΔΕΥΤΕΡΑ

    • Time and Space bounds, multiple strings, linear speedup, nondeterminism.
    • The Universal Turing Machine, Simulation, Diagonalization The Halting Problem, Recursive and Recursive Enumerable Sets, Rice’s Theorem.



    ΠΕΜΠΤΗ

    • Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem, Succinct Certificates.
    • Space Computation: The classes L and NL, Savitch's Theorem, NL-completeness.


    Reading:
    -Ch.3, 7 from [1]