Slajdy (definice, tvrzení)

• slides

Doporučená literatura

• Michael Sipser: Introduction to the Theory of Computation, PWS Publishing Company 1996
• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press (elektronická verze knihy není úplná)

Monografie

• Jose Luis Balcazar, Josep Diaz, Joaquim Gabarro: Structural Complexity I,II, Springer Verlag 1995
• Daniel Pierre Bovet, Pierluigi Crescenzi: Introducition to the Theory of Complexity, Prentice Hall 1993
• Michael R. Garey, David S. Johnson: Computers and Intractability: a Guide to the Theory of NP-completness, W.H.Freeman and Company, San Francisco, 1979
• Lane A. Hemaspaandra, Mitsumori Ogihara: The Complexity Theory Companion. Springer, 2005
• Christos H. Papadimitriou: Computational Complexity, Addison-Wesley 1994
• Uwe Schonig, Randall Pruim: Gems of Theoretical Computer Science, Springer Verlag, 1998
• Ingo Wegener: Complexity Theory (Exploring the Limits of Efficient Algorithms, Springer 2003
• Dexter Kozen: Theory of Computation. Springer 2006
• Maribel Fernández" Models of Computation. Springer 2009 

On-line knihy a weby

• Alan Turing
• The Alan Turing Year
• Gödel’s Lost Letter and P=NP
• Complexity ZOO
• P versus NP page
• Ingo Wegener: The Complexity of Boolean Functions
• Johan Hastad: Complexity Theory
• Pierluigi Crescenzi and Viggo Kann: A compendium of NP optimization problems
• Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo: Limits to Parallel Computation: P-Completeness Theory
• Richard Ladner: Complexity Theory Lectures
• Oded Goldreich: Introduction to Complexity Theory
• Luca Trevisan Lecture Notes in Computational Complexity

Blogy

• Computational complexity
• The Blog of Scott Aaronson
• Theoretical Computer Science on Stackexchange
• What Is The Last Question?

Přehledové články

• Lance Fortnow:  The Status of the P versus NP Problem  (pdf na web page L. Fortnowa)
• Lance Fortnow: Beeyond NP: The Work and Legacy of Larry Stockmeyer
• R.E Stearns:  Juris Hartmanis: The beginnings of computational complexity
• Russel Impagliazzo: A personal view of average case complexity
• Avi Widgerson:  P, NP and Mathematics - a computational complexity perspective
• Scott Aaronson: P=?NP
• Scott Aaronson: Why Philosophers Should Care About Computational Complexity
• Scott Aaronson:  NP-complete Problems and Physical Reality
• Scott Aaronson: The Ghost in the Quantum Turing Machine
• Michael Sipser: The History and Status of the P versus NP Question
• Juraj Hromkovič: Why the Concept of Computational Complexity is Hard for Verifiable Mathematics
• Lane A Hemaspaandra, Ryan Williams: An Atypical Survey of Typical-Case Heuristic Algorithms