Δομική Πολυπλοκότητα
Weekly outline
- Χειμερινό Εξάμηνο 2024-2025
Χειμερινό Εξάμηνο 2024-2025
Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Αντώνης Αντωνόπουλος, συνεργαζόμενος ερευνητής (aanton@corelab.ntua.gr)
Βοηθοί Διδασκαλίας:
- Σταύρος Πετσαλάκης, Υ/Δ (spetsalakis@corelab.ntua.gr)
Διαλέξεις:
- Δευτέρα 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
Εβδομάδα 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
Εβδομάδα 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]
- 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.
- Εβδομάδα 3
Εβδομάδα 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.
Μπορείτε να διαβάσετε: - Basic notions and results of Complexity Theory: NL-completeness, P-completeness, The Cook-Levin Theorem, NP-completeness, PSPACE-completeness, Logical Characterizations & Descriptive complexity.