10 August 2010

P is not equal to NP ?

A few days ago, Vinay Deolalikar of HP Research Labs, Palo Alto made public a paper claiming that P ≠ NP. The proof in this 100-page document remains to be checked and scrutinized.

If correct, it will be a staggering achievement.

It is quite interesting that the approach of the paper is based on Probability. If correct, it will be a triumph for the author, a triumph for humanity, and a triumph for Probability. We strongly feel that Probability plays a very important role in mainstream Mathematics and, if correct, this result will be yet another affirmation of this feeling.

Let us not forget that the P vs NP Problem is one of the Clay Mathematics Institute Millennium problems.
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)


T H E B O T T O M L I N E

What measure theory is about

It's about counting, but when things get too large.
Put otherwise, it's about addition of positive numbers, but when these numbers are far too many.

The principle of dynamic programming

max_{x,y} [f(x) + g(x,y)] = max_x [f(x) + max_y g(x,y)]

The bottom line

Nuestras horas son minutos cuando esperamos saber y siglos cuando sabemos lo que se puede aprender.
(Our hours are minutes when we wait to learn and centuries when we know what is to be learnt.) --António Machado

 Αγεωμέτρητος μηδείς εισίτω.
(Those who do not know geometry may not enter.) --Plato

Sapere Aude! Habe Muth, dich deines eigenen Verstandes zu bedienen!
(Dare to know! Have courage to use your own reason!) --Kant