Weekly outline

  • Χειμερινό Εξάμηνο 2024-2025

    Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.

    Διδάσκοντες:

    Βοηθοί Διδασκαλίας:

    Διαλέξεις:
    • Δευτέρα 17:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
    • Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)

         Έναρξη μαθημάτων: 7/10/24


    Περιεχόμενο Μαθήματος:
    Basic notions and results in Complexity Theory. Oracles & The Polynomial Hierarchy. The structure of NP. Randomized Computation. Non-Uniform Complexity. Circuit Lower Bounds. Interactive Proofs. Probabilistically Checkable Proofs. Pseudorandomness and Derandomization of Complexity Classes. Circuit Lower Bounds for NEXP. Counting Complexity. A short introduction to Fine-Grained Complexity.


  • Εβδομάδα 1

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

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

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

    • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. 


    Μπορείτε να διαβάσετε:

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

    • Εβδομάδα 2

      Δευτέρα 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]

      • Εβδομάδα 3

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

        • Basic notions and results of Complexity Theory: NL-completeness, P-completeness, The Cook-Levin Theorem, NP-completeness, PSPACE-completeness, Logical Characterizations & Descriptive complexity.


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

        • Oracles & The Polynomial Hierarchy: Oracles and oracle classes, Oracle worlds.

        Μπορείτε να διαβάσετε:
        • Section 14.3 from [1]
        • Ch. 17 from [1]


        Δείτε επίσης:

        • Εβδομάδα 4

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

          Δεν έγινε μάθημα.


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

          • Oracles & The Polynomial Hierarchy: The Polynomial Hierarchy, definition and properties.


          Μπορείτε να διαβάσετε:

          • Ch. 17 from [1]


          • Εβδομάδα 5

            Δευτέρα 4 Νοεμβρίου

            • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FPNP.


            Πέμπτη 7 Νοεμβρίου

            • The Structure of NP: Enumerations, Ladner’s Theorem.


            Μπορείτε να διαβάσετε:
            • Ch. 17 from [1]
            • Sections 14.1-14.2 from [1]

            • Εβδομάδα 6

              Δευτέρα 11 Νοεμβρίου

              • The Structure of NP: Enumerations, Applications of Ladner’s Theorem and effective presentability, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.


              Πέμπτη 14 Νοεμβρίου

              Δεν έγινε μάθημα.


              Μπορείτε να διαβάσετε:

              • Sections 14.1-14.2 from [1]
              • Sections 2.6 from [2]