You are here

The Golden Ticket: P, NP and the Search for the Impossible

Publisher: 
Princeton University Press
Number of Pages: 
176
Price: 
26.95
ISBN: 
9780691156491

I was surprised and curious to get to review Lance Fortnow’s book, which is based on his marvelous cover article in the Communications of the ACM (CACM) on the P vs NP Millennium problem. The P vs NP problem is a fundamental problem in computer science: does every algorithmic problem with efficiently verifiable solutions have efficiently computable solutions?

As the author says in the Introduction, the CACM article was a hit: it is the most downloaded ever from CACM, the leading print and online publication for the computing and information technology fields. I agree that this level of interest is an invitation to develop the subject into a book. I found the article a pleasure to read, so I dove into the book with mixed feelings: are there added topics? how deeply can one dig into the subject without spoiling it with too many technical details?

The author used the article as a framework for the book, so that sections of the article became chapters: the Beautiful World, P and NP, the Hardest Problems in NP, the Prehistory of P and NP, dealing with Hardness, proving that N is different from NP, Secrets, Quantum, and the Future.

After reading the book, I am grateful to professor Fortnow, first for having accepted the invitation of Moshe Vardi, editor-in-chief of CACM, to write the article, and second for accepting the invitation of many CACM readers to expand it into a book. I particularly enjoyed the chapters on secrets and zero-knowledge proofs and on the prehistory, where I learned that Knuth got fun suggestions like “hard-boiled” (in honor of Cook) as a possible name for the hardest problems in NP.


Celina Miraglia Herrera de Figueiredo is a professor at the Systems Engineering and Computer Science Program of COPPE at the Federal University of Rio de Janeiro. Her main interests are analysis of algorithms and problem complexity, graph theory, and perfect graphs.

Date Received: 
Sunday, January 27, 2013
Reviewable: 
Include In BLL Rating: 
Lance Fortnow
Publication Date: 
2013
Format: 
Hardcover
Audience: 
Category: 
General
Celina Miraglia Herrera de Figueiredo
04/30/2013
BLL Rating: 

NULL

Publish Book: 
Modify Date: 
Wednesday, March 20, 2013

Dummy View - NOT TO BE DELETED