Papadimitriou. Computational Complexity
Body of knowledge for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the structural…
- from
- Theoretical Computer Science
- added
- 2026-10-10
- likes
- 0
similar
-
Walter Dean. Computational Complexity Theory and the Philosophy of Mathematics academic.oup.com
It highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones.
-
Moore & Mertens. The Nature of Computation nature-of-computation.org
It spans complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and of quantum computing. It provides accessible explanations
-
Stanford Encyclopedia of Philosophy. Computational Complexity Theory plato.stanford.edu
The foundations of complexity theory, and its potential significance on philosophy of computer science, philosophy of mathematics and epistemology.
-
Goldreich. Computational Complexity: A Conceptual Perspective wisdom.weizmann.ac.il
A grad introduction to computation complexity theory, emphasizing the idea behind concepts of complexity theory.
-
Demaine, Gasarch & Hajiaghayi. Computers and Intractability: A Guide to Algorithmic Lower Bounds hardness.mit.edu
A sequel to Garey and Johnson's Computers and Intractability: A Guide to NP-Completeness. New topics include Parameterized Complexity, Lower bounds on approximation, Other hardness assumptions (ETH, 3SUM-conjecture, APSP-conjecture, UGC, Others), Online Algorithms, Streaming…
-
Rudich & Wigderson. Computational Complexity Theory ams.org
Three weeks of lectures from the IAS/Park City Mathematics Institute Summer School on computational complexity. Topics include reductions, lower-bounds, average-case complexity, randomness, interactive proof systems, probabilistically checkable proofs, quantum computing, and…
Theoretical Computer Science › Computational Complexity > Introductory > Books: “Body of knowledge for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the structural…”