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

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.