Raphael Rosen, “Math Geek: From Klein Bottles to Chaos Theory, a Guide to the Nerdiest Math Facts, Theorems, and Equations.” Adams Media, a division of F+W Media Inc. www.adamsmedia.com.
On one side of the computer science building on the Princeton University campus, a pattern of protruding bricks can be detected in the brick facade. The pattern is an ASCII equivalent of an equation that the researchers inside the building recognize as P=NP.
The formula is more a concept. P refers to problems that can be solved quickly by mathematicians and computer scientists. NP refers to problems that, for now, appear to have no solutions. If P=NP, then we should be able — especially with the help of computers — to solve all problems. If P≠NP, then there will remain some problems that the most superlative of supercomputer cannot solve.
It’s a concept that so vexing to mathematicians and computer scientists that a $1 million prize has been offered by the Clay Mathematics Institute in Cambridge, Massachusetts, to anyone who can provide a proof of either theorem.
One of the definitive books addressing P and NP is “The Golden Ticket,” written by Georgia Institute of Technology professor Lance Fortnow and published by the Princeton University Press in 2013. Now comes another book, “Math Geek,” written by Raphael Rosen, a science writer in the office of communications at the Princeton Plasma Physics Lab, which offers fun and easily accessible discussions of dozen of mathematical puzzles. Rosen’s book contains two chapters that highlight the P=NP problem:
Delivering Packages Efficiently — The Traveling Salesman Problem
When you get a package from UPS, you might think that math has nothing to do with its getting to your door. In fact, mathematics now plays an important role in how the guys in the brown trucks deliver packages.
At the heart of UPS’s operations is the process of determining the shortest route that any particular driver can take. UPS has around 96,000 delivery vehicles — ranging from cars to vans to motorcycles to alternative-fuel vehicles — and each driver visits, on average, 150 destinations every day. A driver going even one mile more than necessary on a delivery route costs the company millions of dollars per year. The incentive to make each route as short and efficient as possible is huge.
This kind of problem — finding the best possible route — is well known to mathematicians, who call it the Traveling Salesman problem. The name was coined in the days when door-to-door sales were more common; a salesman who had to visit a certain number of households in one day had to figure out the route that took him to each household in the least amount of time. Traveling Salesman problems are difficult to solve because the number of factors that must be taken into account is staggeringly high. For instance, if a driver is scheduled to visit 25 locations during his day, the number of possible routes is 15 trillion trillion. But by using computers and algorithms — sets of instructions designed for a specific purpose — UPS can whittle down the number of possible routes in a short amount of time.
UPS’s efforts to perfect its algorithms ramped up in the 2000s with the creation of a computer program called ORION (On-Road Integrated Optimization and Navigation). ORION’s mathematical calculations have saved UPS drivers millions of miles every year. You might do this in your own life, if you have a series of errands to run — you mentally calculate the most efficient route to make each stop, minimizing time and energy-wasters such as retracing your steps or venturing into a busy spot during rush hour.
Traveling Salesman: The Movie. The Traveling Salesman problem has made it to the silver screen. In 2012 a movie called, appropriately enough, Traveling Salesman focused on four mathematicians who must decide whether to give the United States military a solution to the P=NP problem, knowing that the release of their work would have moral implications, since once the military had the solution it would be able to crack any code in the world, giving it unprecedented power.
Candy Crush Saga
In the past few years, mathematicians have discovered that a popular game being played today on Facebook and mobile devices is actually an example of one of the most difficult problems in the math universe. Math gurus have proved that the game, Candy Crush Saga, is a so-called NP problem, meaning that there is no simple, direct way to solve it, though the solution is easy to verify. NP problems are distinguished from P problems, which can be quickly solved.
Computer scientists and mathematicians would love to determine once and for all whether P problems and NP problems are fundamentally the same; that is, whether each problem that one can verify easily is also a problem that one can solve easily. The P versus NP problem has been designated a Millennium Prize Problem by the Clay Mathematics Institute, and whoever determines whether or not P=NP will win a cool million dollars.
Now one of the most popular games in Facebook and mobile devices, Candy Crush Saga features a game board with candies of different colors, including yellow lemon drops and red jellybeans. Players move the candies either horizontally or vertically to create a group of three of the same candy.
Problem reduction researchers analyzed the mathematics behind Candy Crush in part by using a technique called problem reduction, in which one problem is converted into another one. Problem reduction helps mathematicians determine how difficult a problem is to solve. If the new problem can be reduced to the original problem, then both can be considered equally difficult.
About the author: Raphael Rosen, a philosophy major at Williams College who has a master’s degree in specialized journalism from the Annenberg School at the University of Southern California, caught the science writing bug while working at the Exploratorium, San Francisco’s hands-on museum of science, art, and human perception. There he was inspired by the way the Exploratorium’s exhibits communicated science ideas clearly and in a down-to-earth fashion. (The giant ball bearing and wave interference exhibits stand out in his memory.)
Always interested in the ways in which science and writing intersect, he has been inspired by Jerry P. King, author of “The Art of Mathematics,” as well as K.C. Cole, Philip Hoare, and Bryan Magee.