Υπολογιστική Πολυπλοκότητα
Section outline
-
Προσφέρεται ως "Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Αναπλ. Καθηγητής (pagour@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
- Αγγελική Χαλκή, Υ/Δ (achalki@corelab.ntua.gr)
Διαλέξεις:
- Δευτέρα 17:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
- Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
-
ΔΕΥΤΕΡΑ
- Διοικητικά - Διαδικαστικά
- Problems, Algorithms and Languages. Decision and optimization problems.
- Equivalence of Computational Models, Turing Machines.
ΠΕΜΠΤΗ
- Time and Space bounds, multiple strings, linear speedup, nondeterminism.
- Equivalence of Computational Models, Turing Machines, Representation as string
- The Universal Turing Machine, Simulation, Diagonalization The Halting Problem, Recursive and Recursive Enumerable Sets, Rice’s Theorem.
Μπορείτε να διαβάσετε:
-Ch.1,2,3 from [1] -
ΔΕΥΤΕΡΑ
- Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem, Succinct Certificates.
ΠΕΜΠΤΗ
- Space Computation: The classes L and NL, Savitch's Theorem, NL-completeness.
Μπορείτε να διαβάσετε:
-Ch.7 from [1] - Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem, Succinct Certificates.
-
ΔΕΥΤΕΡΑ
- Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL & Undirected REACHABILITY.
ΠΕΜΠΤΗ
- Different types of reductions (logspace, Karp, Cook), Circuits, P-completeness. NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.
Μπορείτε να διαβάσετε:
-Ch.8 from [1] - Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL & Undirected REACHABILITY.
-
ΔΕΥΤΕΡΑ
- Oracles & The Polynomial Hierarchy: Oracles and oracle classes. Oracle worlds.
ΠΕΜΠΤΗ
- Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.
Μπορείτε να διαβάσετε:
-Section 14.3, Ch.17 from [1] - Oracles & The Polynomial Hierarchy: Oracles and oracle classes. Oracle worlds.
-
ΔΕΥΤΕΡΑ
- The Structure of NP: Ladner’s Theorem, padding.
ΠΕΜΠΤΗ
- The Structure of NP: NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets.
Μπορείτε να διαβάσετε:
-Sections 14.1, 14.2 from [1] - The Structure of NP: Ladner’s Theorem, padding.
-
ΔΕΥΤΕΡΑ
- Randomized Computation: Randomized Algorithms, BPP, RP, coRP, ZPP.
ΠΕΜΠΤΗ
Δεν έγινε μάθημα.Μπορείτε να διαβάσετε:
-Sections 7.1, 7.2, 7.3 from [2] - Randomized Computation: Randomized Algorithms, BPP, RP, coRP, ZPP.
-
ΔΕΥΤΕΡΑ
- Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.
ΠΕΜΠΤΗ
- Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Parallel computation (classes NC, RNC, AC, TC).
Μπορείτε να διαβάσετε:
-Sections 7.4, 7.5 from [2]- Sections 6.1 - 6.7 from [2] - Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.
-
ΔΕΥΤΕΡΑ
- Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds and computational learning.
ΠΕΜΠΤΗ
- Circuit Lower Bounds: Counting Circuits (ACC) and lower bounds, non-uniform lower bound for NEXP, Natural Proofs.
Μπορείτε να διαβάσετε:
- Chapter 14 from [2] - Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds and computational learning.
-
ΔΕΥΤΕΡΑ
- Hierarchies of Complexity Classes (Survey Talk)
ΠΕΜΠΤΗ
ΔΕΝ ΕΓΙΝΕ ΜΑΘΗΜΑ. - Hierarchies of Complexity Classes (Survey Talk)
-
ΔΕΥΤΕΡΑ
- Hierarchies of complexity classes (survey talk cont'd)
ΠΕΜΠΤΗ
- Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, Public and private coins, Arthur-Merlin Games.
Μπορείτε να διαβάσετε:
-Sections 8.1, 8.2 from [2] - Hierarchies of complexity classes (survey talk cont'd)
-
ΔΕΥΤΕΡΑ
- Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].
ΠΕΜΠΤΗ
- Derandomization of Complexity Classes: Pseudorandom Generators, the Nisan-Wigderson Construction, Derandomization vs. Circuit Lower Bounds, The Easy Witness Lemma,
Satisfiability vs Circuit Lower Bounds.
Μπορείτε να διαβάσετε:
-Sections 8.3, 8.4 from [2]- Chapter 20 from [2] - Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].
-
ΔΕΥΤΕΡΑ
- Counting Complexity: The class #P and #P-completeness, The class ⊕P, Valiant-Vazirani Theorem.
ΠΕΜΠΤΗ
- Counting Complexity: Toda’s Theorem.
Μπορείτε να διαβάσετε:
- Chapter 18 from [1] OR Chapter 17 from [2] - Counting Complexity: The class #P and #P-completeness, The class ⊕P, Valiant-Vazirani Theorem.