Θεωρητική Πληροφορική ΙΙ: Υπολογιστική Πολυπλοκότητα (ΣΗΜΜΥ, ΣΕΜΦΕ)
Δομική Πολυπλοκότητα (ΜΠΛΑ)
εαρινό εξάμηνο 2007-2008

● Γενικά ● Ανακοινώσεις ● Υλικό ●

Γενικά

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Άρης Παγουρτζής, Λέκτορας ()

Έναρξη μαθήματος

18/3/2008.

Διαλέξεις

  • Τρίτη 16:00-18:00, αίθουσα 04 Νέο Κτήριο Ηλεκτρολόγων (ΕΜΠ)
  • Πέμπτη 18:00-20:00, αίθουσα 1.1.29 (παλαιό) Κτήριο Ηλεκτρολόγων (ΕΜΠ)

Προαπαιτούμενα

Μαθήματα σε Θεωρία Υπολογισιμότητας και Αλγόριθμους και Πολυπλοκότητα.

Περιεχόμενο μαθήματος

  • Ορισμός κλάσεων πολυπλοκότητας με βάση τις ακόλουθες παραμέτρους:
    • Υπολογιστικό μοντέλο (προγράμματα σε γλώσσα υψηλής βαθμίδος, μηχανές Turing κτλ.),
    • Τρόπος υπολογισμού (ντετερμινιστικό, μη ντετερμινιστικό, πιθανοτικό, κβαντικό κτλ.),
    • Περιορισμοί πόρων (πολυωνυμικός χρόνος, λογαριθμικός χώρος, σταθερός αριθμός επεξεργαστών, κτλ.)
  • Σχέσεις μεταξύ κλάσεων πολυπλοκότητας. Ιεραρχίες (Πολυωνυμική, προσεγγιστική, κ.ά.)
  • Αναγωγές και Πληρότητα. Cook και Karp reducibility. Αναγωγές μεταξύ συναρτήσεων.
  • Προσεγγισιμότητα και μη προσεγγισιμότητα. Approximation preserving reductions.
  • P vs. NP. Ισομορφισμός, μαντεία, μονότονα κυκλώματα.
  • Πολυπλοκότητα εύρεσης Ισορροπιών Nash. PPAD-πλήρη προβλήματα. Κλάση PLS.
  • Παράλληλοι υπολογισμοί. Μοντέλα. Κλάσεις NC και RNC.
  • Λογαριθμικός χώρος. Το πρόβλημα LBA. Symmetric logspace.
  • Η πολυωνυμική ιεραρχία. Προβλήματα βελτιστοποίησης. Κλάση OptP.
  • Μετρητικές κλάσεις και κλάσεις συναρτήσεων. Κλάσεις #P, GapP, TotP. Η κλάση SPP και το πρόβλημα Ισομορφισμού Γράφων. Προσεγγισιμότητα #P προβλημάτων.
  • Πολυωνυμικός χώρος, εκθετικός χρόνος. Παίγνια και διαλογικά πρωτόκολλα. Πιθανοτικά ελέγξιμες αποδείξεις (PCP).

Βιβλιογραφία

  1. S. Arora and B. Barak, Complexity Theory: A Modern Approach, 2008, Princeton University. (draft available here.)
  2. O. Goldreich, Computational Complexity: A Conceptual Perspective, 2008, Cambridge University Press. (draft available here.)
  3. L. A. Hemaspaandra and M. Ogihara, The Complexity Theory Companion, 2002, Springer.
  4. L. Trevisan, Lecture Notes in Computational Complexity, 2002, UC Berkeley.
  5. S. Homer and A. L. Selman, Computability and Complexity Theory, 2001, Springer.
  6. C. H. Papadimitriou, Computational Complexity, 1994, Addison Wesley.
  7. M. R. Garey and D. S. Johnson, Computers and Intractability - A guide to the theory of NP-completeness,1979, Freeman.

Πληροφορίες

  • Ε. Ζάχος, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 11.15. Τηλ. 210 7721646 - 44, fax: 210 772 1645, email: .
  • Α. Παγουρτζής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 11.30. Τηλ. 210 7721644, fax: 210 772 1645, email: .

Ανακοινώσεις

Υλικό

Παρουσιάσεις

1/4 (Β. Μπαμπάς) §§ 1.1.1, 1.3 από το "The Complexity Theory Companion" (Hemaspaandra-Ogihara). Διαφάνειες
3/4 (Γ. Καούρη) L. Fortnow and S. Homer. "A Short History of Computational Complexity". Διαφάνειες
8/4 (Α. Γκόμπελ) §§ 5.1-5.4, 5.7 από το "Computability and Complexity Theory" (Homer-Selman). Διαφάνειες
15/4 (Γ. Καούρη) "A Short History of Computational Complexity" (συνέχεια).
17/4 (Α. Αχιλλέως) O. Reingold. "Undirected ST-Connectivity in Log-Space". Διαφάνειες
6/5 (Α. Τέντες) UMD "Complexity Theory" course, Lecture 11 (IP=PSPACE). Διαφάνειες
8/5 (Β. Κυρίτσης) GATech "Probabilistically Checkable Proofs and Hardness of Approximation" course, Lecture 2 (The PCP Theorem) and Lecture 3 (Hardness of Set Cover). Κεφ. 10 από το "Approximation Algorithms for NP-Hard Problems" (ed. Dorit Hochbaum). Κεφ. 29 από το "Approximation Algorithms" (Vijay V. Vazirani). Διαφάνειες
13/5 (Β. Κυρίτσης) (συνέχεια)
15/5 (Β. Κυρίτσης) (συνέχεια)
20/5 (Γ. Πιερράκος) On the complexity of search problems. C.H. Papadimitriou. "On The Complexity of the Parity Argument and Other Inefficient proofs of Existence". N. Megiddo, C.H. Papadimitriou. "On total functions, existence theorems and computational complexity". D.S. Johnson, C.H. Papadimitriou, M. Yannakakis. "How easy is local search?". C. Daskalakis, P.W. Goldberg, C.H. Papadimitriou. "The Complexity of Computing a Nash Equilibrium". A. Fabrikant, C.H. Papadimitriou, K. Talwar. "The Complexity of Pure Nash Equilibria". "Computational Complexity" (Papadimitriou). Διαφάνειες
22/5 (Β. Κυρίτσης) (συνέχεια)
27/5 (Γ. Πιερράκος) (συνέχεια)
29/5 (Γ. Πιερράκος) (συνέχεια)
29/5 (Α. Γκόμπελ) Polynomial-Time hierarchy. Διαφάνειες
3/6 (Γ. Πιερράκος) (συνέχεια)
5/6 (Α. Γκόμπελ) (συνέχεια)
10/6 (Α. Αχιλλέως) A potpourri from descriptive complexity. Διαφάνειες
24/6 (George Barmpalias-Victoria University, Wellington) Algorithmic Randomness and Computability.
26/6 (Α. Αχιλλέως) (συνέχεια)

Τελευταία ανανέωση: 20 Σεπτεμβρίου 2008