Tuesday, January 30, 2018

Doing Your Sums

Ordinarily math shows things fitting together in a predictable and orderly fashion. One object added to another object makes a pair of objects. Our intuition and experience of the world suggest the outcome of this operation, and when we apply math to it we find out that our intuition was right.

Except when it isn't. Mathematician Julian Havil offers several scenarios in which the "usual thing" produces the exact opposite of what intuition and experience suggest in his 2007 book Nonplussed! He also outlines the mathematics behind events that should be impossible -- like, for example, why a cone can roll uphill, unaided by outside forces.

Oddball things like these generally involve much more complicated math than simple arithmetic. Havil, who taught math at Winchester College for more than 30 years, is quite well equipped to lay out the various formulas that show why, for example, the 13th of a month is more likely to be a Friday than any other day of the week. Or why a bad sports team can improve its performance by adding worse players than its opponents do.

Nonplussed! is, in fact, pretty formula heavy. Havil has written on this topic in some other books and also on other numerical and mathematical topics, but this particular volume is aimed at readers with a basic working knowledge of calculus. He sets up the problems verbally, but in explaining how the counterintuitive results come about he leans much more heavily on equations that will make little sense to those without such knowledge. It doesn't really harm the book but it does significantly limit the potential audience.
-----
Very broadly speaking, there are two kinds of math problems in the world: Ones which can easily be solved by a computer and one whose solutions can be easily checked by a computer. "Solved" in this sense means "proven to be true for any value of the variable." Checked means that if a number is plugged into the equation, it can be seen if the equation still makes sense or if it produces an impossible answer.

The set of solvable equations is called P. The set of checkable equations is called NP. And one of the biggest questions in mathematics, one whose solution could make the world a completely different place, is does P = NP? Georgia Tech computer science professor Lance Fortnow has spent much of his career considering this problem and writes about some of the history of its investigation in 2013's The Golden Ticket: P, NP and the Search for the Impossible.

Current mathematical thought suggests that P ≠ NP, although it can't yet prove that to be true. Fortnow outlines what kind of solutions to world problems might happen if P = NP, such as a wide range of cures for cancer not now possible. It would also make some things significantly more difficult, such as online security. Current online security relies on equations that can't be easily solved because of the number of digits they use and immense number of possible number combinations. But in a P = NP world, those equations could be solved and so computer security would become much more complicated.

Fortnow also describes some of the history of different attempts to determine whether we live in a world where P = NP or where P ≠ NP. He offers some thoughts on what the development of quantum computing, which is projected to be immensely faster than current computing, might mean about getting a definitive answer either way. He keeps the formula and equation use to a minimum, saving much of it for appendices for the readers interested in that part of the story.

The Golden Ticket is a great introduction to a math problem that few people know about and even fewer understand, and a good way to try to start thinking about it and its implications. Although Fortnow doesn't delve much into the philosophical implications of the P, NP problem, he provides enough of the basic tools for the curious to begin that part of the journey themselves.

No comments: