It may be a surprise to some that there are theoretical limits on a computer’s ability. Don’t worry, your next phone will run Angry Birds and Ingress faster than today. But a program that is given another program as input, will never decide whether that program will terminate or run forever. This is known as the halting problem and while it may not practically sound that limiting, it shows that there indeed are limits to what can be done with a computer.
Then there are classes of problems for which there are no known efficient solutions. Even worse, it is not known whether there can be an efficient solutions for these problems. Among computer scientists, this is known as the problem and it is this problem that Lance Fortnow has devoted his new book, The Golden Ticket, to explaining.
As a computer science student, I expected to find this book interesting. But I was pleasantly surprised at the non-technical approach taken by Fortnow. The Golden Ticket instead focuses on the multi-disciplinary aspects of this problems and shows how research in genetics, economics, and of course computer science is frustrated by this open question. He then presents a computational utopia where this problem is solved and how the world will enjoy an explosion of computation, dwarfing the last twenty years. Alas, the utopia is only fiction and Fortnow brings us back to reality by revealing failed attempts at proofs. Not to leave the reader in despair, he then presents the state of the art and direction of technologies pushing computation to its known limits. It turns out the future is not as bleak as this puzzling question.
While this book was certainly written by a computer scientist, it is not for computer scientists. They will, as I did, find it enlightening and appreciate the history of the problems they have formally studied. But I think the audience is much broader and includes anyone who is interested in the limits of our modern computational world. This book details the implications of the greatest unanswered problems in computer science, if not all of mathematics, and anyone with an interest in either subject will find The Golden Ticket a good read.
- Can there be an algorithm for every human desire? (newscientist.com)