Today I’ve stumbled over the news that the mathematician and researcher Vinay Deolalikar working at the Hewlett-Packard Labs in Palo Alto, California has solved the P vs. NP problem! Oneindia News, Telegraph.co.uk and Spektrumdirekt (article in German) resported about this. In Vinay Deolalikar’s 108 pages long paper he possibly proved that P is not equal to NP. Basically this means that there is a class of computationally hard problems (really difficult NP problems), which cannot be solved in polynomial time, but for which at least solutions can be verified in polynomial time. There is no shortcut which would allow you to solve such a problem in polynomial time (see P problems).
Even if the proof is correct, it may still be possible to find a probable solution to a NP problem with a classical computer (see BPP) or a quantum computer (see BQP). This topic is discussed at Mathoverflow.
As far as I see, the core idea of Deolalikar’s proof is that P problems can be broken down into smaller problems, which are independent from each other and can be solved rather quickly. This doesn’t work for all kinds of NP problems, and somehow (using lots of fancy mathematics) from this it should follow that not all NP problems are P problems.
The P vs. NP problem is one of the six (now five?) still unsolved Millenium Prize Problems. If you solve one of these problems you can get 1 Million US$ – be it that the mathematical community is convinced that your proof is correct and you don’t waive that prize like Grigori Perelman who proved the Poincaré conjecture.
- Share to improve your world!
Bookmark on Delicious- Digg this post
- Recommend on Facebook
- Buzz it up
- Share via Reddit
- Subscribe to the comments on this post
