Copyright notice: The following is ACM's copyright notice; other publishers have similar ones.

"Copyright by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted."

Βασικές εργασίες

Τέσσερα υποχρεωτικά αναγνώσματα:

Β. Chazelle. "The algorithm: idiom of modern science".
"Το" Θεώρημα του Cook.
"Το" paper του Karp.
Μ. Sipser. "The History and Status of the P versus NP question".

Διαθέσιμα στο δίκτυο:
A. Wigderson. "The Goedel Phenomena in Mathematics: A Modern View" in "Kurt Goedel and the Foundations of Mathematics: Horizons of Truth", eds. M. Baaz, C. Papadimitriou, H. Putnam, D. Scott, C. Harper, Cambridge University Press, 2010.
E. Allender. "A Status Report on the P versus NP Question" in Advances in Computers Vol. 77 (Marvin Zelkowitz, editor), Academic Press, 2009, pp. 118-147.

Δυο σύντομες εργασίες του Martin Davis που θίγουν κάποια γενικά ζητήματα για την υπολογισιμότητα.

Is Mathematical Insight Algorithmic?
How Subtle is Gödel's Theorem

Μαθήματα, σημειώσεις κοκ
Σημειώσεις του Sanjeev Arora για το μάθημα του στο Princeton. Καλύπτουν κυρίως πιο προχωρημένη ύλη. Περιέχεται σύνδεσμος και στο μάθημα του Luca Trevisan στο Berkeley.

Μια αρχική εκδοχή του βιβλίου του O. Goldreich, "Computational Complexity: A Conceptual Perspective".

Άλλοι ιστοτόποι

Complexity Zoo
Το εξαιρετικό blog του Richard Lipton. Περιέχει συνδέσμους σε άλλα ενδιαφέροντα blogs.

Εκατοντάδες άλλες πηγές είναι διαθέσιμες:, wikipedia.
Επιστροφή στη σελίδα του μαθήματος
Τελευταία ανανέωση: Mon Feb 7 16:35:33 EET 2011