More P v NP

Steve Cook’s Official P versus NP problem Description  for the Clay Mathematics Institute Millennium Prizes

Lance Fortnow’s September 2009 Communications of the ACM article The Status of the P versus NP Problem that inspired this book.

Gödel’s 1956 letter to von Neumann where he essentially describes the P versus NP problem fifteen years before Cook’s seminal paper.


Computational Complexity (Lance Fortnow and Bill Gasarch)

Gödel’s Lost Letter and P=NP (Dick Lipton and Ken Regan)


Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David Johnson. Despite its age, still the best mathematical introduction and reference book on P versus NP and NP-complete problems.

P, NP, and NP-Completeness: The Basics of Computational Complexity by Oded Goldreich. A more technical but still accessible introduction to P versus NP and beyond.

Quantum Computing since Democritus by Scott Aaronson. A fun romp through logic, complexity and  quantum computing. 

Introduction to the Theory of Computation by Michael Sipser. An excellent undergraduate textbook on the basics of theoretical computer science and the P versus NP problem.

Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. A solid graduate text on P, NP and beyond.

Clay Mathematics Institute Lecture on P versus NP by Michael Sipser