Wow! Vinay Deolalikar, a Hewlett Packard researcher, has published his proof that P≠NP. It may not mean much to most of you, but P versus NP is the greatest unsolved problem of theoretical computer science. A complete explanation of the problem would be lengthy, but let me see if I can summarize it.
P represents a large set of computer science problems that are known to be solvable in polynomial time. This means that however large the problem gets — expressed as n, the number of items in the problem — the time it would take to solve it is bounded by some constant multiple of a power of n.
For example, for any given computer, sorting of items is bounded by n2. That is, we can write an expression that includes a constant multiple of n2 that will always be larger than the execution time of the solution. For example, 0.001*n2 seconds would always enough time to sort a list of n names, no matter how big the list got: A million names, a billion names, 6*1023 names, whatever.
(Sorting is actually much more efficient than n2, but it’s not as efficient as n, so n2 is the closest power.)
On the other hand, there are also problems that are not known to be solvable in polynomial time. For example, there’s the traveling salesman problem: Given a set of cities and the travel times between all of them, find the shortest route that visits all cities. The brute force approach of trying all possible combinations is bounded by n!, so solving it for 10 cities takes time proportional to 10*9*8*7*6*5*4*3*2*1. Smarter approaches have lowered the time to 2n. Still, there is no constant power to which n can be raised which will always be larger than 2n, so there are no known polynomial time solutions to the traveling salesman problem.
The traveling salesman problem is only one of many problems which are classified as NP-hard for which it’s possible to create hypothetical algorithms that solve the problem in polynomial time by using a magic guessing step called an oracle that always chooses the correct next step. (I’ve always assumed the oracle character in The Matrix referred to this kind of oracle.) This oracle is a stand-in for a really smart solution that we haven’t figured out yet. The NP-hard problems are related, so that if we find an algorithm that makes one of them solvable in polynomial time, all of them will be solvable in polynomial time. If that happens, then there will be no problems in the set NP that are not also in the set P. In other words, P=NP.
Most complexity theorists think that the reason we haven’t found an algorithmic replacement for the oracle is that none exists. The set NP contains problems that can never be solved in polynomial time. In other words, P≠NP. However, this has never been proven.
Until now. Maybe.
I’m not nearly smart enough to analyze Vinay Deolalikar’s 100-page paper in which he claims to have proven P≠NP, however the smart betting, according to Steven Landsburg, is that it is
a) not crazy (which already puts it in the top 1% of papers that have addressed this question),
b) teeming with creative ideas that are likely to have broad applications, and
c) quite likely wrong.
That last is just a guess, based on the long history of this problem. Unlike the hoard of crazy people who have announced solutions, Deolalikar’s solution might be for real. But the odds are against it.
And in breaking news, while I was writing this, Deolalikar removed the paper from his website.
Leave a Reply