Proof of P≠NP?
Monday, 09 August 2010

The question of P not equalling NP (P≠NP) is probably the most important in computer science and there is a $1 million  prize offered for a proof. The waiting might be over and a lone researcher at HP might have the million dollar proof.

Banner

 

The problem of proving that P is not equal to NP is probably the most important and well known problem in computer science. (See the Related Reading section for articles on what NP and P are all about.)

 

Deolalikar

 

Now Vinay Deolalikar, a well known researcher in networks and complexity theory from HP Labs, has produced a paper that claims to prove P does not equal NP. If nothing else the solution to the problem is big news because it is one of the Millennium Prize Problems and hence associated with a one million dollar prize for the person who solves it.

Deolaliker worked on the problem in his spare time and when he finally made his "breakthrough" he sent the paper as an email to a number of different "leading researchers"  in various areas. The news was made public in an informal blog and the paper was published on the web, apparently without Deolalikar's knowledge. You can read the paper following the link below.

Of course most computer scientists have long believed that NP was different from P - it just seems reasonable that it should be so. However, in the past long held "beliefs" have been overturned when a real proof was discovered and so there was, and perhaps still is, the nagging doubt that NP and P might be the same. If this was so then the effects might be serious as most codes are based on the distinction.

Currently the status of the paper is not settled - is it a proof or does it contain a flaw. Normally this sort of question is settled by peer review and this can take time. The Internet has speeded things up but it has also made it more difficult to know when an erroneous, or even a crackpot, proof is being hailed as the solution to some prestigious problems.

In this case the author has a suitable track record. Along with other researchers, he proved that P was smaller than NP for infinite time Turing Machines. This reduces the chances that the paper is spurious,  but it will still be some time before a final verdict is reached.

The most academically reliable discussion of the paper can be found on Prof. Richard Lipton's blog A Proof That P Is Not Equal To NP?

Deolaliker states that a final version of the paper will be available on his web page in about a week.

At the moment the early draft can be read at pnp12pt.pdf

Further Reading

Computational Complexity

Computability

 

Banner


Google Play Services 6.5
19/11/2014

Google Play services 6.5 includes enhanced features in Google Maps, Drive and Wallet as well as the recently launched Google Fit API. For developers it introduces "granular dependency management", a m [ ... ]



Polyfills As A Service
07/11/2014

Polyfills - don't you just hate'm, but you can't live without them. The big problem is knowing when you need them. Now there is a solution that gets it just right every time.


More News

<ASIN:0521424267>

<ASIN:0262033844>

<ASIN:0716710455>

<ASIN:0201000237>

<ASIN:0805071660>

Last Updated ( Monday, 09 August 2010 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.