Skip to main content

The Golden Ticket: P, NP, and the Search for the Impossible – Lance Fortnow ***

There is good and bad news early on in this book about the P versus NP problem that haunts computing. The good news is that on the description I expected this to be a dull, heavy going book, and it’s not at all. Lance Fortnow makes what could be a fairly impenetrable and technical maths/computing issue light and accessible.
The bad news is that frustratingly he doesn’t actually tell you what P and NP mean for a long time, just gives rather sideways definitions of the problem along the lines of ‘P refers to the problems we can solve quickly using computers. NP refers to the problems to which we would like to find the best solution’, and also that he makes a couple of major errors early on, which make it difficult to be one hundred percent confident about the rest of the book.
The errors come in a section where he imagines a future where P=NP has been proved. This would mean you could write an algorithm to very efficiently match things and select from data. Fortnow suggests that our lives would be transformed. This is slightly cringe-making as fictional future histories often are, but the real problem is that he tells us that the algorithm would make it possible to do two things that I think just aren’t true.
First he says that from DNA you would be able to identify what a person looks like and their personality. Unfortunately, these are both strongly influenced by epigenetic/environmental issues. Anyone who knows adult identical twins (with the same basic DNA) will know that they can look quite different and certainly have very different personalities. And they will usually have been brought up in the same environment. Fortnow is forgetting one of the oldest essentials of computing – it doesn’t matter how good your algorithm is, GIGO – garbage in; garbage out.
The other, arguably worse error is that he says that it will be possible to have accurate weather forecasts going forward X days. This is so horribly wrong. He should have read my book Dice World. The reason you can’t predict the weather at all beyond about 10 days is nothing to do with the quality of the model/algorithm, it is because the system is chaotic. Firstly we just don’t know, and never can know, the initial conditions to enough decimal places not to deviate from the real world. When Lorenz first discovered chaos it was because he entered the starting values in his model to 4 decimal places rather than the 6 to which the model actually worked. It soon deviated from the previous run. We can’t measure things accurately enough. The other problem is that the weather system is so complex – hence the slightly misleading title of Lorenz’s famous paper Does the flap of a butterfly’s wings in Brazil set off a tornado in Texas? – that we can’t possible take into account enough inputs to ever have so good a model as to go forwards that far. Sorry, Lance, it ain’t going to happen.
For the rest, the first half or so of the book goes along pretty well, gradually opening up the nature of P and NP, the problems that are of interest and the ‘hardest’ NP complete problems. I found the main example, used throughout, a hypothetical world called Frenemy where everyone is either a friend or enemy of everyone else confusing and not particularly useful, but Fortnow gets plenty of good stuff in. After that it’s as if he rather runs out of material and it gets a bit repetitious or has rather tangential chapters.
Overall, despite the flaws, a much better and more readable book than I thought it was going to be – but probably best for maths/computing buffs rather than the general popular science audience.
Review by Brian Clegg


Popular posts from this blog

A Tale of Seven Scientists - Eric Scerri ***

Scientists sometimes tell us we're in a post-philosophy world. For example, Stephen Hawking and Leonard Mlodinow in The Grand Design bluntly say that that philosophy is 'dead' - no longer required, as science can do its job far better. However, other scientists recognise the benefits of philosophy, particularly when it is applied to their own discipline. One such is Eric Scerri, probably the world's greatest expert on the periodic table, who in this challenging book sets out to modify the philosophical models of scientific progress.

I ought to say straight away that A Tale of Seven Scientists sits somewhere on the cusp between popular science and a heavy duty academic title. For reasons that will become clear, I could only give it three stars if rating it as popular science, but it deserves more if we don't worry too much about it being widely accessible.

One minor problem with accessibility is that I've never read a book that took so long to get started. First t…

Four Way Interview - Tom Cabot

Tom Cabot is a London-based book editor and designer with a background in experimental psychology, natural science and graphic design. He founded the London-based packaging company, Ketchup, and has produced and illustrated many books for the British Film Institute, Penguin and the Royal Institute of British Architects. Tom has held a lifelong passion to explain science graphically and inclusively ... ever since being blown away by Ray and Charles Eames’ Powers of Ten at an early age. His first book is Eureka, an infographic guide to science.

Why infographics?
For me infographics provided a way to present heavy-lifting science in an alluring and playful, but ultimately illuminating, way. And I love visualising data and making it as attractive as the ideas are.  The novelty of the presentation hopefully gets the reader to look afresh. I love the idea of luring in readers who might normally be put off by drier, more monotone science – people who left science behind at 16. I wanted the boo…

Einstein's Greatest Mistake - David Bodanis ****

Books on Einstein and his work are not exactly thin on the ground. There's even been more than one book before with a title centring on Einstein's mistake or mistakes. So to make a new title worthwhile it has do something different - and David Bodanis certainly achieves this with Einstein's Greatest Mistake. If I'm honest, the book isn't the greatest on the science or the history - but what it does superbly is tell a story. The question we have to answer is why that justifies considering this to be a good book.
I would compare Einstein's Greatest Mistake with the movie Lincoln -  it is, in effect, a biopic in book form with all the glory and flaws that can bring. Compared with a good biography, a biopic will distort the truth and emphasise parts of the story that aren't significant because they make for a good screen scene. But I would much rather someone watched the movie than never found out anything about Lincoln - and similarly I'd much rather someon…