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

Ancestral Night (SF) - Elizabeth Bear *****

Only a couple of weeks ago, reviewing a 1960s SF book, I bemoaned the fact that science fiction novels of ideas are less common now. Although it is correctly labelled a space opera, Ancestral Night delivers ideas with aplomb.

Let's deal with the space opera aspect first. Elizabeth Bear provides some excellent adventure scenes in space, and we've the usual mix of huge spaceships and interesting aliens. Main character Haimey Dz is an engineer on a ship that salvages wrecks - but, as we gradually discover - she also has a forgotten past. A major feature of the storyline (one that seems to link to the medieval idea of the lost wisdom of the past) is ancient technology from a long-dead race with capabilities, notably manipulating spacetime mentally (Bear has yet to point out that the travel technologies used here could manipulate time as well as space), which fit well with Arthur C. Clarke's magic definition.

I particularly liked the (surely intentional) nods to the much-misse…

The Creativity Code - Marcus du Sautoy *****

At first glance this might just be another 'What AI is good at and not so good at' title. And in a way, it is. But, wow, what a brilliant book! Marcus du Sautoy takes us on a tour of what artificial intelligence has achieved (and possibly can in the future achieve) in a range of fields from his own of mathematics, through game playing, music, art and more.

After a little discussion of what creativity is, we start off with the now very familiar story of DeepMind's AlphaGo and its astonishing ability to take on the hugely challenging game of Go. Even though I've read about this many times before, du Sautoy, as a Go player and mathematician, gives a real feel for why this was such a triumph - and so shocking. Not surprisingly he is also wonderful on what mathematicians actually do, how computers have helped them to date and how they have the potential to do far more in the future. After all, mathematics is by far the closest science to game playing, as it has strict rule…

The Demon in the Machine - Paul Davies *****

Physicists have a habit of dabbling in biology and, perhaps surprisingly, biologists tend to be quite tolerant of it. (I find it hard to believe the reverse would be true if biologists tried to do physics.) Perhaps one reason for that tolerance is Schrödinger’s lecture series and book What is Life?, which had a huge impact on molecular biology and with a reference to which, not surprisingly, Paul Davies begins his fascinating book. 

At the heart of the The Demon in the Machine (we'll come back to that demon in a moment) is the relationship between life and information. In essence, Davies points out that if we try to reduce life to its simple physical components it is like trying to work with a computer that has no software. The equivalent of software here is information, not just in the best publicised aspect of the information stored in the DNA, but on a far broader scale, operating in networks across the organism.
This information and its processing gives life its emergent compl…