Βιβλιογραφία - Υλικό - Σύνδεσμοι

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

  1. Christos Papadimitriou, Computational Complexity, Addison Wesley, 1994
  2. Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009
  3. Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008

  4. L. Trevisan, Lecture Notes in Computational Complexity, 2002, UC Berkeley.
  5. 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
  6. Johan Håstad, Lecture Notes on Complexity Theory, 2009

Επιπλέον Υλικό

Σύντομη Εισαγωγή στην Θεωρία Υπολογιστικής Πολυπλοκότητας (Σ. Ζάχος, Ά. Παγουρτζής, Δ. Φωτάκης)

Παράδειγμα 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

Σύνδεσμοι

Μπορείτε να δείτε τα εξής πολύ ενδιαφέροντα papers σχετικά με την Υπολογιστική Πολυπλοκότητα:

Complexity Blogs

Electronic Journals

Complexity Courses

Other Links

Τελευταία τροποποίηση: Wednesday, 5 January 2022, 4:52 PM