http://www.newscientist.com/article/dn19287-p--np-its-b... 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... /
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>