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.

Hardback:  

Kindle:  
Using these links earns us commission at no cost to you
Review by Brian Clegg
Labels:

Comments

Post a Comment

Popular posts from this blog

The Meteorite Hunters - Joshua Howgego *****

This is an extremely engaging read on a subject that everyone is aware of, but few of us know much detail about. Usually, if I'm honest, geology tends to be one of the least entertaining scientific subjects but here (I suppose, given that geo- refers to the Earth it ought to be astrology... but that might be a touch misleading). Here, though, there is plenty of opportunity to capture our interest. The first part of the book takes us both to see meteorites and to hear stories of meteorite hunters, whose exploits vary from erudite science trips to something more like an Indiana Jones outing. Joshua Howgego takes us back to the earliest observations and discoveries of meteorites and the initial doubt that they could have extraterrestrial sources, through to explorations of deserts and the Antarctic - both locations where it tends to be easier to find them. I, certainly, had no idea about the use of camera networks to track incoming meteors, which not only try to estimate where they wi...
Post a Comment
Read more

Against the Odds - John Gribbin and Mary Gribbin ****

The number of women working in STEM subjects has expanded dramatically, but as John and Mary Gribbin make clear, in the history of science this is a very recent occurrence. Here, they bring us the stories of 12 women, from Eunice Newton Foote, born in 1819, to Vera Rubin, born in 1928 - effectively covering nearly 200 years in that Rubin died as recently as 2016. There are some names that will already be familiar from popular science histories (and deservedly so). You will find, for instance, Dorothy Hodgkin and Rosalind Franklin represented. But there are plenty like Foote that few will have come across, including Inge Lehmann, Chien-Sung Wu and Lucy Slater. While arguably Foote is there primarily to demonstrate the difficulties she faced (her discovery of an aspect of greenhouse gas behaviour was independently bettered within weeks), the rest have all made significant discoveries or developments against the odds and often missed out the recognition the deserved. The most prominent ob...
Post a Comment
Read more

Phenomena - Camille Juzeau and the Shelf Studio ****

I am always a bit suspicious of books that are highly illustrated or claim to cover 'almost everything' - and in one sense this is clearly hyperbole. But I enjoyed Phenomena far more than I thought I would. The idea is to cover 125 topics with infographics. On the internet these tend to be long pages with lots of numbers and supposedly interesting factoids. Thankfully, here the term is used in a more eclectic fashion. Each topic gets a large (circa A4) page (a few get two) with a couple of paragraphs of text and a chunky graphic. Sometimes these do consist of many small parts - for example 'the limits of the human body' features nine graphs - three on sporting achievements, three on biometrics (e.g. height by date of birth) and three rather random items (GNP per person, agricultural yields of various crops and consumption of coal). Others have a single illustration, such as a map of the sewers of Paris. (Because, why wouldn't you want to see that?) Just those two s...
Post a Comment
Read more