鈥淒EAR Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.鈥 So began an email sent in August 2010 to a group of leading computer scientists by Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California.
It was an incendiary claim. Deolalikar was saying he had cracked the biggest problem in computer science, a question concerning the complexity and fundamental limits of computation. Answer the question 鈥淚s P equal to NP?鈥 with a yes, and you could be looking at a world transformed, where planes and trains run on time, accurate electronic translations are routine, the molecular mysteries of life are revealed at the click of a mouse 鈥 and secure online shopping becomes fundamentally impossible. Answer it with a no, as Deolalikar claimed to have done, and it would suggest that some problems are too irreducibly complex for computers to solve exactly.
Advertisement
One way or another, then, we would like an answer. But it has been frustratingly slow in coming. 鈥淚t鈥檚 turned out to be an incredibly hard problem,鈥 says Stephen Cook of the University of Toronto, Canada, the computer scientist who first formulated it in May 1971.
The importance of P = NP? was emphasised in 2000, when the privately funded Clay Mathematics Institute in Cambridge, Massachusetts, named it as one of seven 鈥淢illennium Prize鈥 problems, with a $1 million bounty for whoever solves it. Since then, Cook and other researchers in the area have regularly received emails with purported solutions. Gerhard Woeginger of the Eindhoven University of Technology in the Netherlands even maintains an online list of them. 鈥淲e鈥檝e seen hundreds of attempts, and we can more or less classify them according to the mistakes the proof makes,鈥 he says.
Deolalikar鈥檚 attempt seemed different. For a start, it came from an established researcher rather than one of the legion of amateurs hoping for a pop at glory and a million dollars. Also, Cook initially gave it a cautious thumbs up, writing that it seemed to be a 鈥渞elatively serious claim鈥. That led it to spread across the web and garnered it widespread attention in the press.
In the end, though, it was a false dawn. 鈥淚t probably didn鈥檛 deserve all the publicity,鈥 says Neil Immerman, a computer scientist at the University of Massachusetts, Amherst. He was one of an army of researchers who, working in an informal online collaboration, soon exposed fundamental flaws in the proof.
The consensus now is that his proof 鈥 like all attempts before it 鈥 is unfixable. And so the mystique of P = NP? remains unbroken almost half a century after it was first formulated. But what is the problem about? Why is it so important, and what happens if it is answered one way or the other?
What is P?
Computing power, we are accustomed to think, is the gift that keeps on giving. Every year or two that goes by sees roughly a doubling in our number-crunching capabilities 鈥 a march so relentless that it has acquired the label 鈥淢oore鈥檚 law鈥, after the Intel researcher, Gordon Moore, who first noted the trend back in the 1960s.
Talk of the ultimate limits of computation tends to be about how many transistors, the building blocks of microprocessors, we can cram onto a conventional silicon chip 鈥 or whatever technology or material might replace it. P = NP? raises the spectre that there is a more fundamental limitation, one that lies not in hardware but in the mechanics of computation itself.
P = NP should not be mistaken for a simple algebraic equation 鈥 if it were, we could just have N = 1 and claim the Clay institute鈥檚 million bucks. P and NP are examples of 鈥渃omplexity classes鈥, categories into which problems can be slotted depending on how hard it is to unravel them using a computer.
Solving any problem computationally depends on finding an algorithm, the step-by-step set of mathematical instructions that leads us to the answer. But how much number-crunching does an algorithm need? That depends on the problem.
The P class of problems is essentially the easy ones: an algorithm exists to solve them in a 鈥渞easonable鈥 amount of time. Imagine looking to see if a particular number appears in a list. The simplest solution is a 鈥渓inear search鈥 algorithm: you check each number in turn until you find the right one. If the list has n numbers 鈥 the 鈥渟ize鈥 of the problem 鈥 this algorithm takes at most n steps to search it, so its complexity is proportional to n. That counts as reasonable. So too do things that take a little more computational muscle 鈥 for instance, the manual multiplication of two n-digit numbers, which takes about n2 steps. A pocket calculator will still master that with ease, at least for relatively small values of n. Any problem of size n whose solution requires n to the power of something (nx) steps is relatively quick to crack. It is said to be solvable in 鈥減olynomial time鈥, and is denoted P.
What is NP?
Not all problems are as benign. In some cases, as the size of the problem grows, computing time increases not polynomially, as nx, but exponentially, as xn 鈥 a much steeper increase. Imagine, for example, an algorithm to list out all possible ways to arrange the numbers from 1 to n. It is not difficult to envisage what the solutions are, but even so the time required to list them rapidly runs away from us as n increases. Even proving a problem belongs to this non-polynomial class can be difficult, because you have to show that absolutely no polynomial-time algorithm exists to solve it.
鈥淭he mystique of the problem remains unbroken half a century after it was first formulated鈥
That does not mean we have to give up on hard problems. With some problems that are difficult to solve in a reasonable time, inspired guesswork might still lead you to an answer whose correctness is easy to verify. Think of a sudoku puzzle. Working out a solution can be fiendishly difficult, even for a computer, but presented with a completed puzzle, it is easy to check that it fulfils the criteria for being a valid answer (see diagram). Problems whose solutions are hard to come by but can be verified in polynomial time make up the complexity class called NP, which stands for non-deterministic polynomial time.
Constructing a valid sudoku grid 鈥 in essence asking the question 鈥淐an this number fill this space?鈥 over and over again for each space and each number from 1 to 9, until all spaces are compatibly filled 鈥 is an example of a classic NP problem, the Boolean satisfiability problem. Processes such as using formal logic to check software for errors and deciphering the action of gene regulatory networks boil down to similar basic satisfiability problems.
And here is the nub of the P = NP? problem. All problems in the set P are also in the set NP: if you can easily find a solution, you can easily verify it. But is the reverse true? If you can easily verify the solution to a problem, can you also easily solve it 鈥 is every problem in the set NP also in P? If the answer to that question is yes, the two sets are identical: P is equal to NP, and the world of computation is irrevocably changed 鈥 sudoku becomes a breeze for a machine to solve, for starters. But before we consider that possibility, what happens if P is found to be not equal to NP?
What if P 鈮 NP?
In 2002, William Gasarch, a computer scientist at the University of Maryland in College Park, asked 100 of his peers what they thought the answer to the P = NP? question would be. 鈥淵ou hear people say offhand what they think of P versus NP. I wanted to get it down on record,鈥 he says. P 鈮 NP was the overwhelming winner, with 61 votes. Only nine people supported P = NP, some, they said, just to be contrary. The rest either had no opinion or deemed the problem impossible to solve.
鈥淧roving P = NP would have the curious side effect of rendering mathematicians redundant鈥
If the majority turns out to be correct, and P is not equal to NP 鈥 as Deolalikar suggested 鈥 it indicates that some problems are by their nature so involved that we will never be able to crunch through them. If so, the proof is unlikely to make a noticeable difference to you or me. In the absence of a definitive answer to P = NP?, most computer scientists already assume that some hard problems cannot be solved exactly. They concentrate on designing algorithms to find approximate solutions that will suffice for most practical purposes. 鈥淲e鈥檒l be doing exactly the same as we鈥檙e currently doing,鈥 says Woeginger.
Proving P 鈮 NP would still have practical consequences. For a start, says Immerman, it would shed light on the performance of the latest computing hardware, which splits computations across multiple processors operating in parallel. With twice as many processors, things should run twice as fast 鈥 but for certain types of problem they do not. That implies some kind of limitation to computation, the origin of which is unclear. 鈥淪ome things seem like they鈥檙e inherently sequential,鈥 says Immerman. 鈥淥nce we know that P and NP are not equal, we鈥檒l know why.鈥
It could also have an impact on the world of cryptography. Most modern encryption relies on the assumption that breaking a number down to its prime-number factors is hard. This certainly looks like a classic NP problem: finding the prime factors of 304,679 is hard, but it鈥檚 easy enough to verify that they are 547 and 557 by multiplying them together. Real encryption uses numbers with hundreds of digits, but a polynomial-time algorithm for solving NP problems would crack even the toughest codes.
So would P 鈮 NP mean cryptography is secure? Not quite. In 1995, Russell Impagliazzo of the University of California, San Diego, sketched out five possible outcomes of the P = NP? debate. Four of them were shades-of-grey variations on a world where P 鈮 NP. For example, we might find some problems where even though the increase in complexity as the problem grew is technically exponential, there are still relatively efficient ways of finding solutions. If the prime-number-factoring problem belongs to this group, cryptography鈥檚 security could be vulnerable, depending where reality lies on Impagliazzo鈥檚 scale. 鈥淧roving P is not equal to NP isn鈥檛 the end of our field, it鈥檚 the beginning,鈥 says Impagliazzo.
Ultimately, though, it is the fifth of Impagliazzo鈥檚 worlds that excites researchers the most, however unlikely they deem it. It is 鈥淎lgorithmica鈥 鈥 the computing nirvana where P is indeed equal to NP.
Constructing a valid sudoku grid 鈥 in essence asking the question 鈥淐an this number fill this space?鈥 over and over again for each space and each number from 1 to 9, until all spaces are compatibly filled 鈥 is an example of a classic NP problem, the Boolean satisfiability problem. Processes such as using formal logic to check software for errors and deciphering the action of gene regulatory networks boil down to similar basic satisfiability problems.
And here is the nub of the P = NP? problem. All problems in the set P are also in the set NP: if you can easily find a solution, you can easily verify it. But is the reverse true? If you can easily verify the solution to a problem, can you also easily solve it 鈥 is every problem in the set NP also in P? If the answer to that question is yes, the two sets are identical: P is equal to NP, and the world of computation is irrevocably changed 鈥 sudoku becomes a breeze for a machine to solve, for starters. But before we consider that possibility, what happens if P is found to be not equal to NP?
What if P 鈮 NP?
In 2002, William Gasarch, a computer scientist at the University of Maryland in College Park, asked 100 of his peers what they thought the answer to the P = NP? question would be. 鈥淵ou hear people say offhand what they think of P versus NP. I wanted to get it down on record,鈥 he says. P 鈮 NP was the overwhelming winner, with 61 votes. Only nine people supported P = NP, some, they said, just to be contrary. The rest either had no opinion or deemed the problem impossible to solve.
鈥淧roving P = NP would have the curious side effect of rendering mathematicians redundant鈥
If the majority turns out to be correct, and P is not equal to NP 鈥 as Deolalikar suggested 鈥 it indicates that some problems are by their nature so involved that we will never be able to crunch through them. If so, the proof is unlikely to make a noticeable difference to you or me. In the absence of a definitive answer to P = NP?, most computer scientists already assume that some hard problems cannot be solved exactly. They concentrate on designing algorithms to find approximate solutions that will suffice for most practical purposes. 鈥淲e鈥檒l be doing exactly the same as we鈥檙e currently doing,鈥 says Woeginger.
Proving P 鈮 NP would still have practical consequences. For a start, says Immerman, it would shed light on the performance of the latest computing hardware, which splits computations across multiple processors operating in parallel. With twice as many processors, things should run twice as fast 鈥 but for certain types of problem they do not. That implies some kind of limitation to computation, the origin of which is unclear. 鈥淪ome things seem like they鈥檙e inherently sequential,鈥 says Immerman. 鈥淥nce we know that P and NP are not equal, we鈥檒l know why.鈥
It could also have an impact on the world of cryptography. Most modern encryption relies on the assumption that breaking a number down to its prime-number factors is hard. This certainly looks like a classic NP problem: finding the prime factors of 304,679 is hard, but it鈥檚 easy enough to verify that they are 547 and 557 by multiplying them together. Real encryption uses numbers with hundreds of digits, but a polynomial-time algorithm for solving NP problems would crack even the toughest codes.
So would P 鈮 NP mean cryptography is secure? Not quite. In 1995, Russell Impagliazzo of the University of California, San Diego, sketched out five possible outcomes of the P = NP? debate. Four of them were shades-of-grey variations on a world where P 鈮 NP. For example, we might find some problems where even though the increase in complexity as the problem grew is technically exponential, there are still relatively efficient ways of finding solutions. If the prime-number-factoring problem belongs to this group, cryptography鈥檚 security could be vulnerable, depending where reality lies on Impagliazzo鈥檚 scale. 鈥淧roving P is not equal to NP isn鈥檛 the end of our field, it鈥檚 the beginning,鈥 says Impagliazzo.
Ultimately, though, it is the fifth of Impagliazzo鈥檚 worlds that excites researchers the most, however unlikely they deem it. It is 鈥淎lgorithmica鈥 鈥 the computing nirvana where P is indeed equal to NP.
Constructing a valid sudoku grid 鈥 in essence asking the question 鈥淐an this number fill this space?鈥 over and over again for each space and each number from 1 to 9, until all spaces are compatibly filled 鈥 is an example of a classic NP problem, the Boolean satisfiability problem. Processes such as using formal logic to check software for errors and deciphering the action of gene regulatory networks boil down to similar basic satisfiability problems.
And here is the nub of the P = NP? problem. All problems in the set P are also in the set NP: if you can easily find a solution, you can easily verify it. But is the reverse true? If you can easily verify the solution to a problem, can you also easily solve it 鈥 is every problem in the set NP also in P? If the answer to that question is yes, the two sets are identical: P is equal to NP, and the world of computation is irrevocably changed 鈥 sudoku becomes a breeze for a machine to solve, for starters. But before we consider that possibility, what happens if P is found to be not equal to NP?
What if P 鈮 NP?
In 2002, William Gasarch, a computer scientist at the University of Maryland in College Park, asked 100 of his peers what they thought the answer to the P = NP? question would be. 鈥淵ou hear people say offhand what they think of P versus NP. I wanted to get it down on record,鈥 he says. P 鈮 NP was the overwhelming winner, with 61 votes. Only nine people supported P = NP, some, they said, just to be contrary. The rest either had no opinion or deemed the problem impossible to solve.
鈥淧roving P = NP would have the curious side effect of rendering mathematicians redundant鈥
If the majority turns out to be correct, and P is not equal to NP 鈥 as Deolalikar suggested 鈥 it indicates that some problems are by their nature so involved that we will never be able to crunch through them. If so, the proof is unlikely to make a noticeable difference to you or me. In the absence of a definitive answer to P = NP?, most computer scientists already assume that some hard problems cannot be solved exactly. They concentrate on designing algorithms to find approximate solutions that will suffice for most practical purposes. 鈥淲e鈥檒l be doing exactly the same as we鈥檙e currently doing,鈥 says Woeginger.
Proving P 鈮 NP would still have practical consequences. For a start, says Immerman, it would shed light on the performance of the latest computing hardware, which splits computations across multiple processors operating in parallel. With twice as many processors, things should run twice as fast 鈥 but for certain types of problem they do not. That implies some kind of limitation to computation, the origin of which is unclear. 鈥淪ome things seem like they鈥檙e inherently sequential,鈥 says Immerman. 鈥淥nce we know that P and NP are not equal, we鈥檒l know why.鈥
It could also have an impact on the world of cryptography. Most modern encryption relies on the assumption that breaking a number down to its prime-number factors is hard. This certainly looks like a classic NP problem: finding the prime factors of 304,679 is hard, but it鈥檚 easy enough to verify that they are 547 and 557 by multiplying them together. Real encryption uses numbers with hundreds of digits, but a polynomial-time algorithm for solving NP problems would crack even the toughest codes.
So would P 鈮 NP mean cryptography is secure? Not quite. In 1995, Russell Impagliazzo of the University of California, San Diego, sketched out five possible outcomes of the P = NP? debate. Four of them were shades-of-grey variations on a world where P 鈮 NP. For example, we might find some problems where even though the increase in complexity as the problem grew is technically exponential, there are still relatively efficient ways of finding solutions. If the prime-number-factoring problem belongs to this group, cryptography鈥檚 security could be vulnerable, depending where reality lies on Impagliazzo鈥檚 scale. 鈥淧roving P is not equal to NP isn鈥檛 the end of our field, it鈥檚 the beginning,鈥 says Impagliazzo.
Ultimately, though, it is the fifth of Impagliazzo鈥檚 worlds that excites researchers the most, however unlikely they deem it. It is 鈥淎lgorithmica鈥 鈥 the computing nirvana where P is indeed equal to NP.
What if P = NP?
If P = NP, the revolution is upon us. 鈥淚t would be a crazy world,鈥 says Immerman. 鈥淚t would totally change our lives,鈥 says Woeginger.
That is because of the existence, proved by Cook in his seminal 1971 paper, of a subset of NP problems known as NP-complete. They are the executive key to the NP washroom: find an algorithm to solve an NP-complete problem, and it can be used to solve any NP problem in polynomial time.
Lots of real-world problems are known to be NP-complete. Satisfiability problems are one example; versions of the knapsack problem, which deals with optimal resource allocation, and the notorious travelling salesman problem are others. This problem aims to find the shortest-distance route for visiting a series of points and returning to the starting point, an issue of critical interest in logistics and elsewhere.
If we could find a polynomial-time algorithm for any NP-complete problem, it would prove that P = NP, since all NP problems would then be easily solvable. The existence of such a universal computable solution would allow the perfect scheduling of transport, the most efficient distribution of goods, and manufacturing with minimal waste 鈥 a leap and a bound beyond the 鈥渟eems-to-work鈥 solutions we now employ.
It could also lead to algorithms that perform near-perfect speech recognition and language translation, and that let computers process visual information as well as any human can. 鈥淏asically, you would be able to compute anything you wanted,鈥 says Lance Fortnow, a computer scientist at Northwestern University in Evanston, Illinois. A further curious side effect would be that of rendering mathematicians redundant. 鈥淢athematics would be largely mechanisable,鈥 says Cook. Because finding a mathematical proof is difficult, but verifying one is relatively easy, in some way maths itself is an NP problem. If P = NP, we could leave computers to churn out new proofs.
鈥淚t could also lead to algorithms for near-perfect speech recognition and translation鈥
What if P = NP, but there is no algorithm?
There is an odd wrinkle in visions of a P = NP world: that we might prove the statement to be true, but never be able to take advantage of that proof. Mathematicians sometimes find 鈥渘on-constructive proofs鈥 in which they show that a mathematical object exists without actually finding it. So what if they could show that an unknown P algorithm exists to solve a problem thought to be NP? 鈥淭hat would technically settle the problem, but not really,鈥 says Cook.
There would be a similar agonising limbo if a proof that P = NP is achieved with a universal algorithm that scales in complexity as n to the power of a very large number. Being polynomial, this would qualify for the Clay institute鈥檚 $1 million prize, but in terms of computability it would not amount to a hill of beans.
Are we likely to have any definitive answer soon?
When can we expect the suspense to be over, one way or another? Probably not so soon. 鈥淪cientometrist鈥 Samuel Arbesman of the Harvard Medical School in Boston, Massachusetts, predicts that a solution of 鈥淧 = NP?鈥 is not likely to arrive before 2024. In Gasarch鈥檚 2002 poll of his peers, only 45 per cent believed it would be resolved by 2050. 鈥淚 think people are now more pessimistic,鈥 he says, 鈥渂ecause after 10 years there hasn鈥檛 been that much progress.鈥 He adds that he believes a proof could be up to 500 years away.
Others find that excessively gloomy, but all agree there is a mammoth task ahead. 鈥淭he current methods we have don鈥檛 seem to be giving us progress,鈥 says Fortnow. 鈥淎ll the simple ideas don鈥檛 work, and we don鈥檛 know where to look for new tools,鈥 says Woeginger. Part of the problem is that the risk of failure is too great. 鈥淚f you have already built up a reputation, you don鈥檛 want to publish something that makes other people laugh,鈥 says Woeginger.
Some are undeterred. One is Ketan Mulmuley at the University of Chicago. Fellow researchers say his approach looks promising. In essence it involves translating the P= NP? problem into more tractable problems in algebraic geometry, the branch of mathematics that relates shapes and equations. But it seems even Mulmuley is not necessarily anticipating a quick success. 鈥淗e expects it to take well over 100 years,鈥 says Fortnow.
Ultimately, though, Mulmuley鈥檚 tactic of connecting P = NP? to another, not obviously related, mathematical area seems the most promising line of attack. It has been used before: in 1995, the mathematician Andrew Wiles used work linking algebraic geometry and number theory to solve another high-profile problem, Fermat鈥檚 last theorem. 鈥淭here were a lot of building blocks,鈥 says Fortnow. 鈥淭hen it took one brilliant mind to make that last big leap.鈥
Woeginger agrees: 鈥淚t will be solved by a mathematician who applies methods from a totally unrelated area, that uses something nobody thinks is connected to the P versus NP question.鈥 Perhaps the person who will settle P = NP? is already working away in their own specialised field, just waiting for the moment that connects the dots and solves the world鈥檚 hardest problem.