Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα (ΣΗΜΜΥ)
Αλγόριθμοι και Πολυπλοκότητα II (ΜΠΛΑ)
χειμερινό εξάμηνο 2012-2013
Γενικά
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Άρης Παγουρτζής, Επίκ. Καθηγητής ()
Βοηθός διδασκαλίας
- Αντώνης Αντωνόπουλος ()
Έναρξη Μαθήματος
- Δευτέρα, 8 Οκτωβρίου 2012
Διαλέξεις (θεωρία)
- Δευτέρα 17:00-19:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.29)
- Πέμπτη 14:00-16:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.29)
Ώρες γραφείου
- Παρασκευή 12:00-16:00, στο Eργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλιά Κτίρια ΗΜΜΥ, ΕΜΠ.
Διοικητικά
- Περιεχόμενο Μαθήματος-Syllabus (pdf)
- Βαθμολόγηση:
- Γραπτή Εξέταση: 6 μονάδες
- Ασκήσεις: 2 μονάδες
- Ομιλία: 2 μονάδες
- Quizes: 1 μονάδα
Βιβλιογραφία
- Christos Papadimitriou, Computational Complexity, Addison Wesley, 1994
- Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009
- Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008
- L. Trevisan, Lecture Notes in Computational Complexity, 2002, UC Berkeley.
-
E. Allender, M. Loui, and K. Regan, Three chapters for the CRC Handbook on Algorithms and Theory of Computation (M.J. Atallah, ed.), (Boca Raton: CRC Press, 1998).
- Chapter 27: Complexity Classes
- Chapter 28: Reducibility and Completeness
- Chapter 29: Other Complexity Classes and Measures
- Johan Håstad, Lecture Notes on Complexity Theory, 2009
Ανακοινώσεις
- Αποτελέσματα Επαναληπτικής Εξέτασης Φεβρουαρίου 2014
- [NEW! 10/1/2014] H επαναληπτική εξέταση του μαθήματος θα γίνει την Τετάρτη, 5 Φεβρουαρίου 2014 στις 15:00, στο Αμφ. 1 στα Νέα Κτίρια Ηλεκτρολόγων, ΕΜΠ.
- Αποτελέσματα Κανονικής Εξέτασης Μαρτίου 2013
- [7/2/13]
H ύλη του μαθήματος είναι η εξής (Βρίσκεται και εδώ σε .pdf):
1) Από το βιβλίο του Παπαδημητρίου [1] : - Κεφ. 1
- Κεφ. 2: όχι το section 2.6
- Κεφ. 3
- Κεφ. 4: μόνο τα sections 4.1, 4.2
- Κεφ. 5: μόνο το section 5.7
- Κεφ. 7
- Κεφ. 8: όχι την απόδειξη του Θεωρ. 8.3 [Fagin]
- Κεφ. 9
- Κεφ. 10: όχι τo section 10.2
- Κεφ. 12: μόνο το section 12.1, μέχρι την σ. 285
- Κεφ. 14: μόνο τα sections 14.1 (όχι την απόδειξη του θ. 14.1 [Ladner]) και 14.3
- Κεφ. 15: όχι το section 15.1, και όχι ότι έχει σχέση με Parallel RAMs
- Κεφ. 16
- Κεφ. 17: από το section 17.1 μόνο από σ. 416 και μετά, χωρίς τις αποδείξεις των αναγωγών, section 17.2 χωρίς τις αποδείξεις των θ. 17.12 και 17.13
- Κεφ. 18: χωρίς την απόδειξη του θ. 18.3 [Valiant]
- Κεφ. 19: μόνο το section 19.1, μέχρι την σ. 460
2) Από το βιβλίο των Arora-Barak [2] : - Κεφ. 6: χωρίς την απόδειξη του θ. 6.19 [Karp-Lipton], και όχι το section 6.8
- Κεφ. 7
- Κεφ. 8: όχι τα subsections 8.2.2, 8.2.3, και όχι τα sections 8.6 και 8.7
- Κεφ. 11: όχι το section 11.5
3) Άλλα Κείμενα-Διαφάνειες (υπάρχουν στην σελίδα): - [22/1/13] Η εξέταση του μαθήματος θα γίνει την Τρίτη, 12 Μαρτίου 2013, 15:00-18:00, στην αίθουσα A301 στο κτίριο Α της ΣΕΜΦΕ, ΕΜΠ.
- [17/12/12] Την Δευτέρα 17/12 θα έχουμε Quiz στις ενότητες 8.1 και 8.2 από το βιβλίο [1] (Παπαδημητρίου) που αφορούν Reductions και Completeness, και στις ενότητες 7.1, 7.3, 7.4 και 7.5.3 από το βιβλίο [2] (Arora-Barak), που αφορούν Randomized Complexity Classes. Δείτε επίσης και τις διαφάνειες που βρίσκονται εδώ για την κλάση PP και τους χαρακτηρισμούς με ποσοδείκτες.
- [29/10/12] Η Η/Μ παράδοσης για την 1η σειρά Ασκήσεων παρατείνεται για τις 6 Δεκεμβρίου!
- [29/10/12] Την Δευτέρα 5/11 θα έχουμε Quiz στις ενότητες 3.3, 7.1, 7.3.
- [31/10/12] Βαθμοί Εξεταστικής Περιόδου Σεπτεμβρίου 2012
- [29/10/12] Την Δευτέρα 5/11 θα έχουμε Quiz στις ενότητες 3.3, 7.1, 7.3.
- [24/10/12] Tο αυριανό μάθημα (25/10) δεν θα πραγματοποιηθεί.
- [21/10/12] Το αυριανό μάθημα (22/10) θα γίνει 5:15-7:00, στην αίθουσα 1.1.31 στα Παλιά Κτίρια ΗΜΜΥ, ΕΜΠ.
- [17/10/12] Tο αυριανό μάθημα (18/10) θα γίνει 13:15-15:00. Θα συναντηθούμε έξω από το νέο CoReLab (Παλιά κτίρια ΗΜΜΥ, ΕΜΠ, αίθουσα 1.1.3) για να βρούμε αίθουσα!
- [10/10/12] Αύριο Πέμπτη 11/10, το μάθημα θα γίνει 15:00-17:00, στην αίθουσα 1.1.31 (απέναντι από το νέο CoReLab), Παλιά Κτίρια ΗΜΜΥ, ΕΜΠ.
- [8/10/12] Τα μαθήματα άρχισαν. Όποιος δεν γράφτηκε στην mail-list του μαθήματος, μπορεί να το κάνει την επόμενη φορά, ή να στείλει ένα mail στο .
Διαλέξεις - Παρουσιάσεις
| Η/Μ | Ομιλητής | Θέμα - Περιεχόμενο |
|---|---|---|
| 8/10/12 |
Εισαγωγή - Διαδικαστικά Hierarchies of Complexity Classes ♦ Μπορείτε να διαβάσετε το 1ο Κεφάλαιο από το [1]. |
|
| 11/10/12 |
Computational Models, Hierarchies, History ♦ Διαβάστε από το [1] τα sections 1.1, 1.2, 1.3, 1.4 (με έμφαση), 2.1, 2.2, 2.3, 2.4. |
|
| 15/10/12 | Computational Model-Turing Machines: Equivalence of Computational Models, Turing Machines, Time and Space bounds, multiple strings, linear speedup, nondeterminism. | |
| 18/10/12 |
Computability and Undecidability: The Universal Turing Machine,
Simulation, Diagonalization, The Halting Problem, Recursive and Recursive Enumerable Sets. ♦ Διαβάστε το Section 3.3: Rice’s Theorem, Recursive Unseparability. |
|
| 22/10/12 | Complexity Classes: Complexity measures, Time and Space Classes Hierarchy Theorems, Gap Theorem, Basic inclusions between complexity classes, Quantifier Notation and characterization of NP (Theorem 9.1 [1]). | |
| 25/10/12 | Δεν έγινε μάθημα. | |
| 29/10/12 | Χ. Μωυζές (slides) | Space Computation: The classes L and NL, Savitch’s Theorem, Immerman-Szelepscényi Theorem (NL=coNL), Reingold’s Theorem: L=SL (without proof) & Undirected REACHABILITY. |
| 1/11/12 | Α. Γιαννακόπουλος |
Second-Order Logic, Incompleteness, Fagin's Theorem |
| 5/11/12 | Α. Γιαννακόπουλος |
1 o Quiz στις ενότητες 3.3, 7.1, 7.3 Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd) |
| 8/11/12 | Α. Γιαννακόπουλος Δ. Μπάκας (slides) |
Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd) The Arithmetical Hierarchy |
| 12/11/12 | Δ. Χατζηδημητρίου |
Diagonalization & Hierarchies, Case-Study: DTIME(n)⊂DTIME(n1.5) Reductions: Reductions between problems, P-completeness, NP-completeness. |
| 19/11/12 | Δ. Χατζηδημητρίου Α. Μάντης Α. Δαμιανάκης |
Reductions: Different types of reductions (Karp, Cook, Cook[1], tt), and relations among them. NP-Complete Problems: - Cook’s Theorem, SAT and satisfiability variants - IS,CLIQUE, MAX-CUT |
| 22/11/12 | Χ. Πηλιχός (slides) Σ. Τσιούνης |
NP-Complete Problems: - HP, TSP, 3COL, 0/1 IP - 3DM, KNAPSACK, Pseudopolynomial Algorithms and Strong NP-Completeness |
| 26/11/12 | Ι. Νέμπαρης Σ. Μανιάτης |
Ladner’s Theorem, Density, Sparse sets The “Berman-Hartmanis” conjecture, NP-isomorphism, padding. |
| 29/11/12 | Μ. Επιτρόπου (slides) | Function Problems: The classes coNP and ∆NP, Function classes (FL, FP, FNP, FPSPACE etc) and reductions, the classes PLS and PPAD. |
| 3/12/12 | Β. Νάκος | Randomized Computation: Randomized Algorithms, BPP, RP, coRP, ZPP classes |
| 6/12/12 | Oracles & The Polynomial Hierarchy: Oracles and oracle classes, the Polynomial-Time Hierarchy. | |
| 10/12/12 | Δεν έγινε μάθημα. | |
| 13/12/12 | (slides) | Quantifier notation (∃+) and related results, semantic and syntactic classes, the “P vs BPP” question. |
| 17/12/12 |
2o Quiz σε Reductions & Randomized Complexity Classes The equivalence between Oracle and Quantifier Polynomial Hierarchy |
|
| 20/12/12 | (slides) | The Polynomial-Time Hierarchy and related theorems, The BPP Theorem, Swapping quantifiers, Operator-defined classes. |
| 7/1/13 | Δεν έγινε μάθημα. | |
| 10/1/13 | (slides) |
Non-Uniform Complexity: Boolean circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs. |
| 14/1/13 | Χ. Πηλιχός (slides) B. Γιαννακοπούλου |
Parallel computation (classes NC, RNC, AC, TC) Interactive Proof Systems: -Interactive Proofs (IP) |
| 17/1/13 | Β. Γιαννακοπούλου |
Interactive Proof Systems: -Arthur-Merlin Games (AM) |
| 21/1/13 | Γ. Καρυστιανός Γ. Ζηρδέλης |
Interactive Proof Systems: -Shamir’s Theorem: IP=PSPACE -Zero Knowledge Proofs |
| 24/1/13 | (slides) |
Quantifier Notation and Arthur-Merlin Games An introduction to Pseudorandomness and Derandomization Introduction to PCPs |
| 28/1/13 | Μ. Ζαμπετάκης (slides) |
Interactive Proof Systems: -Probabilistically Checkable Proofs (PCP) -Dinur's Proof of the PCP Theorem |
| 31/1/13 | Κ. Νικολιδάκη (slides) Ζ. Πιτουράς (slides) K. Μάστακας (slides) |
Counting Complexity: #P, #P-completeness Toda's Theorem, Gaps, TotP Approximability and Approximation Schemes |
| 4/2/13 | Θ. Λιανέας Σ. Δήμος |
Reingold's Theorem: L=SL Quantum Computation |
| 7/2/13 | Α. Ταουσάκος (slides) Θ. Λυκούρης (slides) Κ. Καραθάνος (slides) Κ. Κοιλιάρης (slides) |
Alternation Interactive Proof Systems: -Hardness of Approximations Pseudorandomness & Combinatorial Constructions The Unique Games Conjecture |
| 11/2/2013 | Β. Ζυγομήτρος (slides) Π. Τελώνη |
Algebraic Computation The Bright Side of Hardness |
Συμπληρωματικό Υλικό
- Σύντομη Εισαγωγή στην Θεωρία Υπολογιστικής Πολυπλοκότητας (Σ. Ζάχος, Ά. Παγουρτζής, Δ. Φωτάκης)
- Παράδειγμα Yλοποίησης Μηχανής Turing
- Quantifier Characterization of Complexity Classes
- A Landscape of Computational Complexity (M. Faramawi, K. Regan)
- A survey of Probabilistically Checkable Proofs (S. Arora)
- Inapproximability of Combinatorial Optimization Problems (L. Trevisan)
- A Landscape of Computational Complexity (M. Faramawi, K. Regan)
- What is a Natural Proof? (Timothy Y. Chow) Published in AMS Notices
Ασκήσεις
| Ασκήσεις | Η/Μ Ανάρτησης | Η/Μ Παράδοσης | Link |
|---|---|---|---|
| 1η Σειρά | 29/10/2012 | 6/12/2012 | |
| 2η Σειρά | 30/12/2012 | 24/1/2013 | |
| 3η Σειρά | 8/2/2013 | 10/3/2013 |
Σύνδεσμοι: Complexity around the World (Wide Web)
Μπορείτε να δείτε τα εξής πολύ ενδιαφέροντα papers σχετικά με την Υπολογιστική Πολυπλοκότητα:
- Complexity Theory-A Survey (Oded Goldreich and Avi Wigderson)
- The Gődel Phenomena in Mathematics: A Modern View (A. Wigderson)
- Knowledge, Creativity and P versus NP (A. Wigderson)
- P, NP and Mathematics - A computational complexity perspective (A. Wigderson)
Complexity Blogs
- In Theory (Luca Trevisan)
- Gödel’s Lost Letter and P=NP (Richard Lipton)
- Computational Complexity (Lance Fortnow & Bill Gasarch)
- Shtetl-Optimized (Scott Aaronson)
- Oded Goldreich's Homepage
- Scott Aaronson's Homepage
Electronic Journals
- Electronic Colloquium on Computational Complexity (ECCC)
- ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT)
Complexity Courses
- PCP and Hardness of Approximation, Berkeley, Spring 2006 (Luca Trevisan)
- Computational Complexity, Berkeley, Spring 2008 (Luca Trevisan)
- Computational Complexity, Princeton, Spring 2007 (Boaz Barak)
- Computational Complexity, Princeton, Spring 2001 (Sanjeev Arora)
- Computational Complexity, Princeton, Spring 2003 (Sanjeev Arora)
- Advanced Complexity Theory, MIT, Spring 2007 (Madhu Sudan)
- Complexity of Computation, Rutgers University, Spring 2007 (Eric Allender)
- Introduction to Computational Complexity, Brown University, Spring 2007 (John E. Savage)
- Quantum Complexity Theory, MIT, Fall 2010 (Scott Aaronson)
- Advanced Complexity Theory, MIT, Spring 2005 (Madhu Sudan)
- Advanced Complexity Theory, MIT, Fall 2001 (Dan Spielman)
- Theory of Computation, MIT, Fall 2006 (Michael Sipser)
- Computational Complexity, TIFR, 2011-12 (Prahladh Harsha)
- Computational Complexity, Stanford University, Spring 2010 (Luca Trevisan)
- Computational Complexity, Tel Aviv University (Muli Safra)
- Computational Complexity, University of Illinois, Spring 2009 (Manoj M. Prabhakaran)
- Boolean Circuit Complexity, Tel Aviv University, Fall 1994-1995 (Uri Zwick)
Other Links
- Resource-Bounded Measure Bibliography (Maintained by John Hitchcock)
- Effective Fractal Dimension Bibliography (Maintained by John Hitchcock)