# In Pursuit of the Impossible Equation

March 04, 2013

Imagine that a typical 9-by-9 Sudoku puzzle (in which the numbers 1 through 9 must appear exactly once in each row, column, and square) has been transformed into a 25-by-25 grid. The number of possibilities increases drastically, but while difficult, the puzzle remains solvable. Now imagine that the game has become a 1,000-by-1,000 behemoth. The chances of finding a solution plummet—in fact, this game can prove too complex for our fastest computers and most-advanced algorithms.

It is this realm of complexity that Lance Fortnow explores in The Golden Ticket: P, NP, and the Search for the Impossible, out this month from Princeton University Press. Fortnow, a professor and chair of the School of Computer Science at the Georgia Institute of Technology, centers his discussion of very, very difficult mathematical problems on the elusive, unsolved theorem "P versus NP." When the Clay Mathematics Institute announced, in 2000, that it would pay \$1-million for the solution of any of seven unsolved mathematical problems, one of them—"P versus NP"—stood out to Fortnow. The reason? Proving P=NP would allow the solver to solve the other six problems.

So what is "P versus NP"? Essentially, P stands for problems with easy solutions (like solving a 9-by-9 Sudoku puzzle). NP stands for the set of very, very difficult problems—say, the 1,000-by-1,000 Sudoku puzzle or the classic "traveling-salesman problem," a challenge in which an algorithm attempts to find the shortest possible route among thousands of destinations. If P were to equal NP, then computationally complex problems (those that often involve analyzing huge amounts of data) could be tackled quickly and easily, as the algorithms used to solve those problems become more efficient.

According to Fortnow, if P=NP, then we inhabit a utopian "beautiful world"—one in which computers defeat cancer, and DNA-based cures are distributed by USB stick. In such a world, computational complexity is no longer a stumbling block, so computer scientists can quickly craft perfect stump speeches by examining large data sets—specifically, all prior successful political speeches. Algorithms could lead a computer to outmanage a human baseball coach by crunching through stats and probabilities.

P=NP does have a downside. Digital encryption would be useless in the face of ruthlessly efficient algorithms that could decipher any code. Employment would suffer a major blow as a large percentage of jobs done by humans could be performed by machines. Such a world, Fortnow speculates, will almost certainly never exist.

The vast majority of computer scientists working on the problem believe that P does not equal NP and are working on proofs that would show that difficult mathematical problems do not have quick and easy solutions. Fortnow is skeptical that we will find such a proof in the near future (a belief echoed by the mathematician Ian Stewart, who put it plainly in a new book: "No one has a clue how to solve it").

When Vinay Deolalikar, of Hewlett-Packard Labs, sent around a paper in 2010 titled simply "PNP," rumors spread rapidly. "Passions have run high," reported The New York Times, and one MIT computer scientist challenged Deolalikar by betting \$200,000 against the success of the proof. (Fortnow notes that computer scientists eventually "found several flaws, minor, major, and fatal.") More recently, Ketan Mulmuley, of the University of Chicago, has pursued a PNP proof based on advanced algebraic geometry. Mulmuley, while initially optimistic, now believes that this approach, if successful at all, could take more than 100 years of work to come to fruition.

And yet while The Golden Ticket deals with a seemingly intractable problem, Fortnow is quick to point out the virtues of attempting to solve it. "P/NP is two separate problems," he explains over the phone. "There's the mathematical issue, but it's also about a way of thinking." The author, who receives a proposed solution at least once a month, explains that, philosophically, the equation encourages us to think about the limits of algorithms. "It's just not the case that you can write a computer program to solve any problem," he allows, "but that's not the end of the story. It's possible to get pretty good solutions." We can learn much from practical, imperfect computer-science techniques like brute force (producing all possible solutions and checking each one), heuristics (using certain general rules of thumb to constrain data), and approximation (allowing inaccuracies in algorithmic attempts). "There are limits to computation, but that doesn't mean the problem you want to solve can't be solved," he says.

Another strategy for computer scientists in a PNP world? Acceptance. "Sometimes a problem just defies solution, and you have to give up and do something else," writes Fortnow.

Still, there's more at stake in The Golden Ticket than mere cognizance of mathematical limitations. There's been a relative dearth of popular computer-science books, and while titles like Beginning Programming for Dummies proliferate, Fortnow wishes to instill a sense that computer science isn't all about building apps or increasing advertising revenue. "It's about getting us to learn how we handle large amounts of data, how we store that data." The book's target reader, he says, is "the high-school science-nerd type, the person who really wants to understand, but without getting into overly technical aspects."

To avoid such "overly technical" aspects, the book is laid out as a series of playful thought experiments regarding possible futures for "P versus NP." In one such experiment, P is proven to equal NP, and a Ph.D. student named Steve revolutionizes several industries with "42 million lines of unintelligible machine code."

At times Fortnow worries that computers have become too easy to use—that we take them for granted. "My biggest fear is that the computer has become like the car. Everyone can drive a car, but people never try to get under the hood." The Golden Ticket urges mathematically minded readers to take on "P versus NP." "I encourage you to try, for you cannot truly understand the difficulty of a problem without attempting to solve it."