Υπολογιστική Πολυπλοκότητα
Περιγραφή εβδομάδας
- Χειμερινό Εξάμηνο 2019-2020
Χειμερινό Εξάμηνο 2019-2020
Προσφέρεται ως "Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (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)
- 30 September - 6 October
30 September - 6 October
ΠΕΜΠΤΗ
- Διοικητικά - Διαδικαστικά
- Problems, Algorithms and Languages. Decision and optimization problems, Representation as strings.
- Equivalence of Computational Models, Turing Machines.
Reading:
-Ch.1,2 from [1] - 7 October - 13 October
7 October - 13 October
ΔΕΥΤΕΡΑ
- Time and Space bounds, multiple strings, linear speedup, nondeterminism.
- The Universal Turing Machine, Simulation, Diagonalization The Halting Problem, Recursive and Recursive Enumerable Sets, Rice’s Theorem.
ΠΕΜΠΤΗ
- 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.
Reading:
-Ch.3, 7 from [1] - 14 October - 20 October
14 October - 20 October
ΔΕΥΤΕΡΑ
- Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL & Undirected REACHABILITY.
ΠΕΜΠΤΗ
- Different types of reductions (logspace, Karp, Cook), Circuits.
Reading:
-Ch.8 from [1] - Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL & Undirected REACHABILITY.
- 21 October - 27 October
21 October - 27 October
ΔΕΥΤΕΡΑ
- P-completeness, NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.
ΠΕΜΠΤΗ
- Oracles & The Polynomial Hierarchy: Oracles and oracle classes. Oracle worlds.
Reading:
-Section 14.3, Ch.17 from [1] - P-completeness, NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.
- 28 October - 3 November
28 October - 3 November
ΔΕΥΤΕΡΑ
- Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.
ΠΕΜΠΤΗ
- Randomized Computation: Randomized Algorithms, BPP, RP, coRP, ZPP.
Reading:
-Sections 7.1, 7.2, 7.3 from [2] - Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.
- 4 November - 10 November
4 November - 10 November
ΔΕΥΤΕΡΑ
- 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.
Reading:
-Sections 7.4, 7.5 from [2]-Sections 6.1-6.6 from [2] - Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.
- 11 November - 17 November
11 November - 17 November
ΔΕΥΤΕΡΑ
- Non-Uniform Complexity: Parallel computation (classes NC, RNC, AC, TC).
- Circuit Lower Bounds: Lower Bounds for AC0, Counting Circuits (ACC) and lower bounds, non-uniform lower bound for NEXP, Natural Proofs.
ΠΕΜΠΤΗ
Δεν έγινε μάθημα.Reading:
-Section 6.7 from [2]- Sections 14.1 - 14.4 from [2] - 18 November - 24 November
18 November - 24 November
ΔΕΥΤΕΡΑ
- Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, public and private coins, Arthur-Merlin Games, the class AM and its properties.
ΠΕΜΠΤΗ
- Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].
Reading:-Ch.8 from [2] - Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, public and private coins, Arthur-Merlin Games, the class AM and its properties.
- 25 November - 1 December
25 November - 1 December
ΔΕΥΤΕΡΑ
- The Structure of NP: Ladner’s Theorem, padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.
ΠΕΜΠΤΗ
- The Structure of NP: density, sparse sets, Mahaney's Theorem
Reading:-Sections 14.1, 14.2 from [1] - The Structure of NP: Ladner’s Theorem, padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.
- 2 December - 8 December
2 December - 8 December
ΔΕΥΤΕΡΑ
- Circuit Lower Bounds: Håstad's Switching Lemma's proof, Natural arguments.
ΠΕΜΠΤΗ
Δεν έγινε μάθημα. - Circuit Lower Bounds: Håstad's Switching Lemma's proof, Natural arguments.
- 9 December - 15 December
9 December - 15 December
ΔΕΥΤΕΡΑ
- Circuit Lower Bounds: Lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bound techniques.
ΠΕΜΠΤΗ
- Derandomization of Complexity Classes: The general derandomization paradigm, Pseudorandom Generators.
- Circuit Lower Bounds: Lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bound techniques.
- 16 December - 22 December
16 December - 22 December
ΔΕΥΤΕΡΑ
- Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness, Uniform Derandomization, consequences to Circuit Lower Bounds.
ΠΕΜΠΤΗ
- Logic Paper Presentation.
- Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness, Uniform Derandomization, consequences to Circuit Lower Bounds.
- 23 December - 29 December
- 6 January - 12 January
6 January - 12 January
ΠΕΜΠΤΗ
- Counting Complexity: The class #P, parsimonious reductions, completeness results.
- Counting Complexity: The class #P, parsimonious reductions, completeness results.
- 13 January - 19 January
13 January - 19 January
ΔΕΥΤΕΡΑ
- Guest Lecture: Smooth Complexity (M. Vlatakis)
ΠΕΜΠΤΗ
- Counting Complexity: The class ⊕P, Valiant-Vazirani Lemma.
- Guest Lecture: Smooth Complexity (M. Vlatakis)
- 20 January - 26 January
20 January - 26 January
ΔΕΥΤΕΡΑ
- Derandomization of Complexity Classes:
The Easy Witness Lemma proof.
ΠΕΜΠΤΗ
- Counting Complexity: Toda's Theorem, the class GapP and applications.
- Derandomization of Complexity Classes:
The Easy Witness Lemma proof.
- 27 January - 2 February
27 January - 2 February
ΔΕΥΤΕΡΑ
- Guest Lecture: 90 years of Computability and Complexity (Stathis Zachos)
ΠΕΜΠΤΗ
Δεν έγινε μάθημα - Guest Lecture: 90 years of Computability and Complexity (Stathis Zachos)
- 3 February - 9 February