Fortnow. The Golden Ticket: P, NP, and the Search for the Impossible
A nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond.
- from
- Theoretical Computer Science
- added
- 2026-10-10
- likes
- 0
similar
-
Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity wisdom.weizmann.ac.il
A very gentle introduction to some fundamental ideas of computational complexity like NP-completeness and P vs NP.
-
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…
-
Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness wisdom.weizmann.ac.il
An introduction to the interwoven domains of cryptography, proofs and randomness.
-
Fortnow & Homer. A Short History of Computational Complexity researchgate.net
A historical overview of computational complexity.
-
Arora. A Theorist's Toolkit. Princeton cs.princeton.edu
Aimed primarily at first and second year graduate students who plan to do research in theoretical computer science. We will introduce probabilistic, algebraic, combinatorial, and algorithmic methods useful in proofs.
-
ObjectivePGP github.com
Theoretical Computer Science › Popular Science: “A nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond.”