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]



              • Εβδομάδα 7

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

                • The Structure of NP: Proof of Ladner’s Theorem, Padding, Density, Sparse Sets, Mahaney's Theorem.


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

                • Randomized Computation: Probabilistic Turing machines, the class BPP. The classes RP, coRP and ZPP. Quantifier notation and related results, the the class ZPP, semantic and syntactic classes, the “P vs BPP” question.


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

                • Εβδομάδα 8

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

                  • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice


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

                  • Non-Uniform Complexity: Karp-Lipton Theorem, Algorithms for Circuit Analysis. Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound.


                  Μπορείτε να διαβάσετε:
                  • Sections 6.1-6.7 from [2]