Δομική Πολυπλοκότητα
Section outline
-
Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Νίκος Λεονάρδος, Επίκ. Καθηγητής (nleon@cs.ntua.gr)
- Αντώνης Αντωνόπουλος, συνεργαζόμενος ερευνητής (aanton@corelab.ntua.gr)
Βοηθοί Διδασκαλίας:
- Σταύρος Πετσαλάκης, Υ/Δ (spetsalakis@corelab.ntua.gr)
Διαλέξεις:
- Δευτέρα 17:15-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
- Πέμπτη 15:15-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
Έναρξη μαθημάτων: 5/10/2026Περιεχόμενο Μαθήματος:
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. -
Week 1
- Basic notions and results of Complexity Theory: Problems, Turing Machines and their properties, Undecidability and Rice's Theorem.
-
Week 2
- Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems.
- 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.
-
Week 3
- Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics, Savitch’s Theorem, Immerman-Szelepscényi Theorem.
- Basic notions and results of Complexity Theory: NL-completeness, P-completeness, The Cook-Levin Theorem, NP-completeness, PSPACE-completeness, Logical Characterizations & Descriptive complexity.
-
Week 4
- Oracles & The Polynomial Hierarchy: Oracles and oracle classes, Oracle worlds, The Polynomial Hierarchy, definition and properties. The complexity of optimization problems, the class FPNP.
- The Structure of NP: Enumerations, Ladner’s Theorem.
-
Week 5
- The Structure of NP: Enumerations, Applications of Ladner’s Theorem and effective presentability, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture. Proof of Ladner’s Theorem, Padding, Density, Sparse Sets, Mahaney's Theorem.
- The Structure of NP: Enumerations, Applications of Ladner’s Theorem and effective presentability, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture. Proof of Ladner’s Theorem, Padding, Density, Sparse Sets, Mahaney's Theorem.
-
Week 6
- 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.
-
Week 7
- Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice
- Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice
-
Week 8
- Non-Uniform Complexity: Karp-Lipton Theorem, Algorithms for Circuit Analysis. Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound.
- Non-Uniform Complexity: Karp-Lipton Theorem, Algorithms for Circuit Analysis. Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound.
-
Week 9
- Non-Uniform Complexity: Lower bounds for ACC0, lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bounds techniques. Monotone functions and circuit lower bounds. Natural proofs: the Circuit Complexity Barrier.