Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity
A very gentle introduction to some fundamental ideas of computational complexity like NP-completeness and P vs NP.
- from
- Theoretical Computer Science
- added
- 2026-10-10
- likes
- 0
similar
-
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…
-
Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness wisdom.weizmann.ac.il
An introduction to the interwoven domains of cryptography, proofs and randomness.
-
Goldreich. Randomized Methods in Computation wisdom.weizmann.ac.il
The aim of the current course is to make the students familiar with some of randomized methods.
-
Papadimitriou. Computational Complexity pearson.com
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…
-
Arora & Barak. Computational Complexity: A Modern Approach theory.cs.princeton.edu
A golden standard textbook, Surveying computational complexity theory for graduate students and researchers.
Theoretical Computer Science › Computational Complexity > Introductory > Books: “A very gentle introduction to some fundamental ideas of computational complexity like NP-completeness and P vs NP.”