A Proof That P Is Not Equal To NP?

[bananas]

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

P ≠ NP? It's bad news for the power of computing
* 14:35 10 August 2010 by Richard Elwes

Has the biggest question in computer science been solved? On 6 August, Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California, sent out draft copies of a paper titled simply "P ≠ NP".

This terse assertion could have profound implications for the ability of computers to solve many kinds of problem. It also answers one of the Clay Mathematics Institute's seven Millennium Prize problems, so if it turns out to be correct Deolalikar will have earned himself a prize of $1 million.

<snip>

Complexity theorists have given a favourable reception to Deolalikar's draft paper, but when the final version is released in a week's time the process of checking it will intensify.

Followed one of the links from there to:

http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/

A Proof That P Is Not Equal To NP?
August 8, 2010
by rjlipton

<snip>

Deolalikar’s draft paper is here—he was kind enough to give me the pointer to his paper. For now please understand that this is a “preliminary version.” See the discussion by Greg Baker, who first posted on his paper.

<snip>

I suggest you look at his paper to see his own summary of his approach, and of course the details of his proof. At the highest level he is using the characterization of polynomial time via finite model theory. His proof uses the beautiful result of Moshe Vardi (1982) and Neil Immerman (1986):

<snip>

[Recursion]

1. Great news for cryptographers

Bad news for cryptanalysts.

It's interesting, though: most of the profs I worked with who dabbled in this all leaned towards P=NP; IIRC a straw poll at some math conference or other had a large majority leaning towards =. Maybe people expected equality so much they didn't look as hard as they could have for a proof of inequality. But, probably not; the author's use of stochastic physical models is apparently quite novel (and interesting, since that's a field I'm into).

[phantom power]

2. That's remarkable -- everybody I ever studied with predicted P != NP.

(I always thought the smart money was on "!=" myself)

[Recursion]

3. Maybe I worked with optimists? NT

[phantom power]

4. LOL -- could be :-)

I recall some speculation that in the event somebody ever proved P = NP, it might or might not change the practical computing landscape much -- if (for example) one derived algorithms via the chains of known completeness proofs, you'd end up with polynomials of enormous exponent :-)

Particularly in light of the fact that good polynomial approximations are known for so many problems anyway.

Either way, I'm really looking forward to finding out if this proof holds up under review!

:toast:

[Recursion]

5. I remember Knuth mentioning the bit about approximations

That it doesn't really matter what the answer is, because for non-marginal use cases we already have very good numeric or other-type approximations for most commonly-encountered traveling-salesman equivalents.