Section outline

  • Δευτέρα 14 Οκτωβρίου

    • Basic notions and results of Complexity Theory: Separating complexity classes via diagonalization, proving inclusion of complexity classes via simulation.  Overview of deterministic and nondeterministic time and space classes. Certificate characterizations.


    Πέμπτη 17 Οκτωβρίου

    • Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics, Savitch’s Theorem, Immerman-Szelepscényi Theorem.


    Μπορείτε να διαβάσετε:
    • Ch. 7 from [1]
    • Ch. 1,2,3 from [2]