Section outline

  • ΔΕΥΤΕΡΑ

    • Διοικητικά - Διαδικαστικά
    • Hierarchies of Complexity Classes (Course overview)
    • Introduction to Complexity Theory.
    • Problems, Algorithms and Languages. Decision and optimization problems.
    • Turing machines with multiple strings, linear speedup, nondeterminism.
    • Equivalence of Computational Models, Turing Machines, Representation as strings.
    • Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization

    ΠΕΜΠΤΗ

    • Introduction to Complexity Theory.
    • Problems, Algorithms and Languages. Decision and optimization problems.