Section outline

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

    • Basic notions and results of Complexity Theory: Problems, Turing Machines and their properties, Undecidability and Rice's Theorem

    Μπορείτε να διαβάσετε:
    • Ch. 1,2,3 from [1]
    • Ch. 0,1 from [2]
    Δείτε επίσης:
    • Στην υποσελίδα "Βιβλιογραφία-Υλικό-Σύνδεσμοι" θα βρείτε τις αναφορές για την βιβλιογραφία ([1], [2]), άλλες πηγές και σημειώσεις διαλέξεων, online courses Πολυπλοκότητας και άλλο ενδιαφέρον υλικό.


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

    • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. Separating complexity classes via diagonalization, proving inclusion of complexity classes via simulation.

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