views:

7735

answers:

8

Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP. Could someone explain how this proof works for us less mathematically inclined people?

+28  A: 

That's brilliant! Some uber-math guy creates a hundred page paper on one of the thorniest problems in CS and you expect a bunch of mere mortals to be able to summarise it into a couple of paragraphs on SO.

Here's how the proof works: it will be peer reviewed by a bucketload of other uber-math geeks and they'll question all the assumptions, all the calculations and probably even the parentage of the author.

Then, if it survives, some other uber-math geeks who specialise in dumbing things down will publish copious quantities of books that we still won't understand.

Eventually, the media will get a hold of it, totally misrepresent what it means and we'll still be none the wiser.

Perhaps in a couple of years, the dust will settle and the essence of the proof will osmote down to those of us working on the coalface. It still won't help the vast majority of code-cutters in dealing with their day-to-day problems like unrealistic expectations and power-mad bosses.

:-)


By way of update, there are some mutterings on possible problems with the proof. This is the "peer-reviewed by a bucketload of other uber-math geeks and they'll question ..." stage I mentioned above.

But, given it contains phrases like:

they all question the author’s deduction that P = NP implies the existence of a polynomial-time algorithm of a certain specific kind, which he then argues leads to a contradiction involving rigorously-known statistical properties of random k-SAT instances, for large enough k.

Well, I think we may still be in the "stuffed if I know" phase :-)

paxdiablo
A hard question isn't a bad question. Don't answer if you don't know. There are lots of smart people on SO.
Nixuz
@Nixuz, feel free to downvote my answer if you think it's unhelpful. That's why it was made CW :-)
paxdiablo
Not everything can be distilled into something comprehensible to the layperson. I'm open to being wrong here, but I strongly suspect this is one of those things. Even if we are all quite smart, most of us simply do not have the many years of advanced research and extremely specialized education necessary to understand this space.
Rex M
I got lost in the third paragraph of the abstract.
Steven A. Lowe
Distilling it down will take some time, if it is true.
starblue
Still, going through *physics* (if I read that part of the summary in the paper right) to prove something in computer science is ... geeky at best. But given the amount of different methods and models used there I wouldn't be surprised if there are still errors at the seams – the very same thing happened to Wiles with Fermats last theorem where the proof was of similar length in the end.
Joey
It's a shame that I cannot downvote this worthless, sarcastic answer as many times as it deserves. You haven't contributed anything.
Andres Jaan Tack
@Andres, that _is_ a crying shame. But I'll make you a promise. As soon as this answer hits zero net votes, I'll delete it. Otherwise you're in the minority, and I'll feel free to ignore your worthless vitriolic comment which contributes even less than my answer :-) If you have a _better_ answer, feel free to post it. This is a meritocracy, after all. With any luck, it will garner more votes and you'll be vindicated. I'll even give you a vote to start you along, just like I have to every other answer here.
paxdiablo
Back to 50's about turing machine: (adapt the words at your will)"Some uber-math guy creates a hundred page paper on one of the thorniest problems in CS and you expect a bunch of mere mortals to be able to summarise it into a couple of paragraphs on SO."
RMAAlmeida
@RMAAx, I'm not saying we'll _never_ understand it. There was a point where we didn't understand flight, or didn't understand what was so damn good about coming down out of the trees, or crawling out of the swamp. We've had a lot of time to get used to the concept of Turing machines.
paxdiablo
@paxdiablo: Though I agree that discussing *this* proof right now is premature (it's not clear even to the author :P), I don't understand your anti-intellectualism or whatever it is: why are you so sure we (or you) will not be able to understand books that come out, for instance? Even the most involved new results in computer science or mathematics can be explained within a month or a few to bright undergraduate students — and usually it just takes, say, a few-hours talk.
ShreevatsaR
Once again, I must point the learned gentleman to the _smiley at the end of my answer!!_ I don't have anti-intellectual tendencies, I've even read GEB and MT from DougH (though I still don't understand all of them).
paxdiablo
I can summarize this question in a couple of sentences: "we don't understand it, we won't understand it for a long time, and when we do it won't really matter. :)" if that's not a sarcastic unhelpful answer, then i'll eat this monitor!
RCIX
@RCIX, that's fine, you're entitled to your opinion as is everyone here. I've stated my position. If you don't like the answer, vote it down and, when it hits zero, I'll delete it and you won't have to worry about it ever again. I've used up enough time answering comments on this question so I'll make this my last.
paxdiablo
Ok, not "anti-intellectual tendencies", but the "we're stupid and we'll never be able to understand" tone, smiley or not. I upvoted this answer because the progression you describe is entirely accurate — right now it's something for the experts, eventually there will be books and popular media misrepresentations — just not the "we still won't understand" part. (For instance all the mathematical content in GEB is perfectly understandable with enough effort.)
ShreevatsaR
+45  A: 

OK so i've only scanned through the paper but heres a rough summary of how it all hangs together.

From page 86 of the paper.

... polynomial time algorithms succeed by successively “breaking up” the problem into smaller subproblems that are joined to each other through conditional independence. Consequently, polynomial time algorithms cannot solve problems in regimes where blocks whose order is the same as the underlying problem instance require simultaneous resolution.

Other parts of the paper show that certain NP problems can not be broken up in this manner. Thus NP/= P

Much of the paper is spent defining conditional independence and proving these two points.

Michael Anderson
+1. Somewhat better than my (facetious) answer but I can't really believe you waded through it to come up with that :-)
paxdiablo
@paxdiablo: I've got a solid maths background, so I took your comment as bit of a challenge. Though its not my area of expertise I also found it an interesting read (though I wont claim more than a skimming of the details)
Michael Anderson
Thank you - and couldn't be happier that you posted this before the question got closed (wrongly in my opinion...)
romkyns
@paxdiablo: no, your answer was more informative, sorry Michael but I don't understand what you're talking about :)
Patrick
+12  A: 

Dick Lipton has a nice blog entry about the paper and his first impressions of it. Unfortunately, it also is technical. From what I can understand, Deolalikar's main innovation seems to be to use some concepts from statistical physics and finite model theory and tie them to the problem.

I'm with Rex M with this one, some results, mostly mathematical ones cannot be expressed to people who lack the technical mastery.

recipriversexclusion
+5  A: 

This is my understanding of the proof technique: he uses first order logic to characterize all polynomial time algorithms, and then shows that for large SAT problems with certain properties that no polynomial time algorithm can determine their satisfiability.

smith
The second part ("and then…") is more or less the statement that P≠NP. :-)
ShreevatsaR
+4  A: 

One other way of thinking about it, which may be entirely wrong, but is my first impression as I'm reading it on the first pass, is that we think of assigning/clearing terms in circuit satisfaction as forming and breaking clusters of 'ordered structure', and that he's then using statistical physics to show that there isn't enough speed in the polynomial operations to perform those operations in a particular "phase space" of operations, because these "clusters" end up being too far apart.

John the Statistician
The proof is being discussed further here: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper
John the Statistician
A: 

It's worth noting that with proofs, "the devil is in the detail". The high level overview is obviously something like:

Some some sort of relationship between items, show that this relationship implies X and that implies Y and thus my argument is shown.

I mean, it may be via Induction or any other form of proving things, but what I'm saying is the high level overview is useless. There is no point explaining it. Although the question itself relates to computer science, it is best left to mathematicians (thought it is certainly incredibly interesting).

Noon Silk
A note: if the high level overview is useless, then you may have gone too high to generate an overview.
RCIX
+8  A: 

I liked this ( http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html ):

His argument revolves around a particular task, the Boolean satisfiability problem, which asks whether a collection of logical statements can all be simultaneously true or whether they contradict each other. This is known to be an NP problem.

Deolalikar claims to have shown that there is no program which can complete it quickly from scratch, and that it is therefore not a P problem. His argument involves the ingenious use of statistical physics, as he uses a mathematical structure that follows many of the same rules as a random physical system.

The effects of the above can be quite significant:

If the result stands, it would prove that the two classes P and NP are not identical, and impose severe limits on what computers can accomplish – implying that many tasks may be fundamentally, irreducibly complex.

For some problems – including factorisation – the result does not clearly say whether they can be solved quickly. But a huge sub-class of problems called "NP-complete" would be doomed. A famous example is the travelling salesman problem – finding the shortest route between a set of cities. Such problems can be checked quickly, but if P ≠ NP then there is no computer program that can complete them quickly from scratch.

Tony Breyal
Except for the mention of statistical physics, this has *nothing* to do with the proof structure here, and is just general blather (but correct) about P versus NP.
ShreevatsaR
+1  A: 

Such proof would have to cover all classes of algorithms ... like continuous global optimization. For example in 3SAT problem we have to valuate variables to fulfill all alternatives of triples of these variables or their negations – look that x OR y can be changed into optimizing

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

and analogously seven terms for alternative of three variables. Finding global minimum of sum of such polynomials for all terms, would solve our problem. (source)

It's going out of standard combinatorial techniques to continuous world using gradient methods, local minims removing methods, evolutionary algorithms ... it's completely different kingdom - numerical analysis - I don't believe such proof could really cover (?)

skeptic
False. If one NP-complete problem is not in P, then the question is answered.
Andres Jaan Tack
You've taken me wrong: I'm talking about class of approaches - if a different one works for 3SAT, all these problems are in P.Continuous global optimization approach makes that we do not longer work on true/false ... but on continuous variables - watching gradient flow in continuous landscape instead of working on discrete sets.
skeptic
As I understand it, he classifies **all** possible algorithms to solve P-problems in polynomial time, then proves that none of them solves 3SAT.
BlueRaja - Danny Pflughoeft
All possible algorithms working on possible solutions ... but here we work literally between them ... I've worked on both complexity and numerical analysis, but I have no idea how to even calculate complexity of such complex continuous global optimization problems???
skeptic