Vinay Deolalikar of HP Labs claims to have solved the P=NP problem. Specifically, he claims they are not equal. A preliminary proof, leaked last Friday:
http://www.scribd.com/mobile/documents/35539144
Apparently several reviewers are claiming his proof is flawed -- but also admit that this proof provides some interesting new views on the problem. So, will Deolalikar claim the million dollar prize or has this preliminary release snatched defeat from the jaws of victory?
funkstar
08-10-10, 08:50 AM
Latest (non-leaked) draft is here. (http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf)
Dick Lipton has a list of the issues raised about the proof on his blog: Gödel's Lost Letter and P=NP (http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/). (I recommend his blog for the computer science interested, btw.)
Google the phrase P=NP, Roubini. "N" is not a multiplier here. This very famous and very hard problem addresses the set of polynomial time algorithms versus the set of non-deterministic polynomial time algorithms. Solving this problem is worth a cool million; it is one of the Clay Math Institute's Millennium Prize Problems.
Roubini
08-12-10, 06:33 AM
I'm actually stunned, given that you've read some of my previous posts, that you think I was being serious.
Only in the case of N=1.
Nonsense.
P=0 is also a solution.
(It's a safe bet I'll never be a millionaire...)
I'm actually stunned, given that you've read some of my previous posts, that you think I was being serious.
Sorry about that. I guess I have a somewhat jaded view of this site; it attracts a *lot* of crackpots.
Jarek Duda
08-13-10, 02:20 AM
Such proof would have to cover all classes of approaches ... 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. (from www .scienceforums.net/topic/49246-four-dimensional-understanding-of-quantum-computers/ )
It's going out of standard combinatorial techniques to continuous world using gradient methods, local minims removing methods, evolutionary algorithms ... it's completely different realm: numerical analysis - I don't believe such proof could really cover (?)
It could work on concrete valuations, but here we work between them.