Χειμερινό Εξάμηνο 2025-2026
Section outline
-
Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Νίκος Λεονάρδος, Επίκ. Καθηγητής (nleon@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)
Έναρξη μαθημάτων: 6/10/25Περιεχόμενο Μαθήματος:
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.