Explain the proof by Vinay Deolalikar that P != NP [closed]

Question

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?

Negatron

I'm voting to close this question as off-topic because it belongs to the Computer Science SE website. – Secretive

Answer 1

I've only scanned through the paper, but here's 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.

Halliehallman

Answer 2

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.

Vaunt

Answer 3

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.

Ranzini

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. – Presbyterial

Answer 4

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.

Marquess

The second part ("and then…") is more or less the statement that P≠NP. :-) – Presbyterial

Answer 5

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.

Riffraff

The proof is being discussed further here: michaelnielsen.org/polymath1/… – Riffraff

Answer 6

Such proof would have to cover all classes of algorithms, like continuous global optimization.

For example, in the 3-SAT problem we have to evaluate 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 the global minimum of a sum of such polynomials for all terms would solve our problem. (source)

It's going out of standard combinatorial techniques to the 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 (?)

Negatron

False. If one NP-complete problem is not in P, then the question is answered. – Block

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. – Geminian

As I understand it, he classifies all possible algorithms to solve P-problems in polynomial time, then proves that none of them solves 3SAT. – Scintillator

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??? – Geminian

Answer 7

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).

Byars

A note: if the high level overview is useless, then you may have gone too high to generate an overview. – Euchromatin