, 2 min read
P equal to NP and all that
One of the better known problems in Computer Science is the P versus NP problem. It is often related to the following question: do all problems for which we can check the correctness of a solution quickly can also be solved quickly.
Most computer scientists believe that P is different from NP. In colloquial terms, this means that we believe that there are problems whose solution can be checked quickly but such that it is very difficult to find the solution.
One relevant problem is the Hamiltonian path problem: given a set of roads and cities, is there a path that visits every city exactly once? It is easy to check any given solution, but it is thought to be quite hard (in general) to find such a solution.
A typical application for our belief that P is different from NP is to show that a given problem is difficult. Proving that something is difficult does not sound very important and practical at first, but it can save your job! There is a million dollar prize to whoever can resolve the P is equal to NP question. This fact alone has attracted much attention to the problem. Whoever solves it would get not only instant fame, but quite a bit of wealth as well.
Lance Fortnow has spent a few years on a book that recounts all the fascinating adventures related to this problem. He explains the problem in depth in an accessible book entitled The Golden Ticket. The book is thoroughly researched and reviewed. Anyone from a smart high school student to a computer scientist is sure to get a lot of this book. The presentation is beautiful. There are few formulas but lots of facts. The book is of course kept simple, so hard-core computational complexity expert might be disappointed, but I think many of them will enjoy the stories Fortnow offer.
Disclosure: I received a free review copy of the book. I am otherwise unrelated to Fortnow.