Vinay Deolalikar says P ≠ NP

Vinay Deolalikar is a research scientist at HP Labs, but today he has become famous for a problem he claims to have solved in his spare time as an independent researcher. The problem in question is the most famous unsolved problem in complexity theory that asks, is P = NP. This is also one of the Clay millennium problems and would win Deolalikar a million dollar prize if his proof is judged to be correct.

This would be the second millennium problem to be solved after the Poincaré conjecture that was solved by Grigori Perelman who refused the prize. Perelman solved the problem while holding a research only position at the Steklov Institute having given up more illustrious fellowships at US institutions that also required him to lecture. We can’t say that Perelman was an independent researcher but he had effectively cut himself off from everything else in order to solve it.

The problem of P = NP relates to the time required for an algorithm to solve a problem with a complexity parameterised by a variable n. If the time taken to solve the problem is a polynomial function of n then the problem is in class P. If the solution once given can be verified in polynomial time then the problem is in class NP. if a problem can be solved in polynomial time then it can certainly be verified in polynomial time so it is easy to see that the class NP contains all problems in class P, so P ⊂ NP. But is P = NP? In other words are there problems that can be verified in non-polynomial time that can’t be solved in polynomial time?

There are plenty examples of problems that appear to answer this question. For example the problem of factorizing an n-digit number. If we are given candidate factors of an n-digit number we can verify them by multiplying them together. Multiplying numbers with less than n digits requires at worst an order of n squared operations so this is in polynomial time, so factorizations are in NP. However, if we want to find a factor, one way would be to search through all possible factors up to the square root of the number. There are 10^(n/2) such numbers so this method cannot provide a polynomial time solution. There are faster algorithms known but none of them use polynomial time. So it looks like this problem is not in P and therefore P ≠ NP, but nobody has ever proved it. If you could find a polynomial time algorithm for factoring numbers then many encryption methods would become very insecure (unless the algorithm has a very large factor or polynomial degree), so this problem has some practical implications.

The factorisation problem is just a small part of the much larger general problem. It is not known (until possibly now) whether any problem exists which is in NP but not P. There are many other candidate problems such as the travelling salesman problem, but it is just very hard to prove that you cannot find a much better problem to solve them than the best ones known.

Deolalikar believes he has now solved this by looking at a type of problem known as k-satisfiability or kSAT. He does this by treating the set of problems as a statistical ensemble and showing that it separates into two phases, one where the problems are in class P and another where they are not. To accomplish this he borrows from finite model theory and uses a powerful result about the Least Fixed Point operator established by Vardi and Immerman in the 1980s. 

The proof is difficult and well outside my area of expertise and we will probably have to wait some time before a consensus forms over its correctness. However, it is clear that the method uses the type of techniques that could solve the problem and the author has published other verified original proofs in the field of complexity before, so the signs are encouraging.

According to information in Wikipedia, Vinay Deolalikar was born in 1971. If that is true it makes him just young enough for the Fields medal which is awarded every four years. Unfortunately the next award will be given this month so it will already have been decided and there wont be time to check his proof anyway. By the time of the next Fields medal he will be too old. It will be interesting to see if he is considered right for any other mathematics prizes of which there are many. It is not often that a mathematician who is not part of an academic institution wins such an award, but such an achievement if it stands up will certainly merit some such recognition.

Update: There are already suggestions that the proof has a flaw involving a confusion about ordered and unordered structures. For more details follow the discussions here, here, here, here and here.

One reason for expert skepticism over Deolalikar’s proof seems to be that there are known reasons why such a proof should be very hard to construct. Just to give a flavour, imagine you want to prove that there is no polynomial time algorithm that can be used to factorise numbers. Your proof would imply that factorisations of numbers are not somehow encoded in the digits of π in a complex way that could be decoded in polynomial time. Yet it is almost impossible to prove even some basic statements about the digits of π.

Of course you might prove that P ≠ NP for some problems within a very large set of possible problems. This could work provided the set is so large that there is not enough space to encode all the solutions in numbers such as π.

It is of course possible that a problem like P = NP could be undecidable, in which case it may or may not be possible to prove that it is undecidable. There are already proofs that show that certain approaches to the problem cannot work. See here for some general information and pointers. One of Hilbert’s original problems was shown to be undecidable and it can be assumed that the Clay prize would be awarded if one of the millennium problems was shown to be undecidable.

2 Responses to Vinay Deolalikar says P ≠ NP

  1. Lawrence B. Crowell says:

    I have not read this with any depth, but only looked at bits and pieces here and there. What is interesting are the connections with statistical mechancis. This is contained in the section “The 1RSB Ansatz of Statistical Mechanics,” and the bit

    d1RSB At some value of α = α_d which is below α_c, it has been observed that the space of solutions splits up into “communities” of solutions such that solutions within a community are close to one another, but are far away from the solutions in any other community. This effect is known as shattering [ACO08]. Within a community, flipping a bounded finite number of variable assignments on one satisfying takes one to another satisfying assignment. But to go from one satisfying assignment in one community to a satisfying assignment in another, one has to flip a fraction of the set of variables and therefore encounters what physicists would consider an “energy barrier” between states. This is the dynamical one step replica symmetry breaking phase.

    This connection with statistical mechanics sounds a lot like the Ising problem. This also makes me wonder whether there are connections with G. Perelman’s set up for the proof of the Poincare conjecture. The opening involves Hamiltonian flows and how it has connections with entropy principles. So all of this does get the neurons working some.

  2. Philip Gibbs says:

    Interest in this news story has gone ballistic. Even this minor post on the subject by me has become my most hit page on this blog for all time.

    Lawrence, I share your interest in the statistical physics aspect of this proof, It reminds me of all sorts of crazy ideas I had about physics in the past.

    Now I have guests arriving soona and have to cut short!

%d bloggers like this: