Δομική Πολυπλοκότητα
Βιβλιογραφία - Υλικό - Σύνδεσμοι
Βιβλιογραφία
[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] J. Katz, Notes on Complexity Theory, 2011, University of Maryland
[6] Jin-Yi Cai, Lectures in Computational Complexity, University of Wisconsin Madison, 2003
[7] 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
Σύνδεσμοι
Online Μαθήματα Υπολογιστικής Πολυπλοκότητας:
- Graduate Complexity Theory at CMU (Ryan O' Donnell)
-
Undergraduate Complexity Theory at CMU (Ryan O' Donnell)
Μπορείτε να δείτε τα εξής 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)