Thursday, August 12, 2010

The P versus NP Millenium Problem

Are you a math lover? You don't have to be mathematician to be one, you know?
And if you are one, then I would recommend The Millenium Problems by Keith Devlin.
From time to time someone will solve one of "the seven greatest unsolved mathematical puzzles of our time" and you could quickly pick this book up and refesh your memory.
And you know where I am coming from, don't you? Yeah the news that is doing rounds: P versus NP Problem Solved?

The P vs. NP problem is listed at number 3 of the 7 unsolved problems by the Clay Mathematics Institute. In his introduction to this problem Keith Devlin writes, "Of all the Millenium Problems, the P versus NP puzzle is the one most likely to be solved by an "unknown amateur" - someone largely untrained in mathematics, possibly someone very young, who is unknown to the mathematical community. ... Not only is it relatively easy to understand what the problem says, it is possible that all it will take to solve it is one good idea. And you don't need lots of knowledge to have a good idea, just imagination."

So, is Vinay Deolaliker that "unknown amateur"? We need to wait and see.
But what is this problem? I fall back to the description in the book by Keith Devlin. And it goes something like this ...

"Computer Scientists divide computational tasks into two main categories: Tasks of type P can be tackled effectively on a computer; tasks of type E could take million years to complete. Unfortunately, most of the big computational tasks that arise in industry and commerce fall into the third category, NP, which seems to be intermediate between P and E. But is it? Could NP be just a disguised version of P? Moswt experts believe that NP and P are not the same. ... But after thirty years of effort, no one has been able to prove whether or not NP and P are the same. A positive solution would have significant implications for industry, for commerce, and for electronic communications, including the World Wide Web."

So what does P and NP stand for? Unlike what seems obvious, they do not stand for "Possible" and "Not Possible"; rather P stands for Polynomial Time processes and NP stands for Nondeterminstic Polynomial-Time processes. And E stands for Exponential-Time processes.

This blog does not claim to understand the problem completely. Nor do I wish to reproduce the lucid explanation of the problem by Keith Devlin. Instead I strongly recommend reading the book. Trying to understand the problem by visiting the Clay Mathematics Institute is an option available only to the mathematicians.

In any case, if you are a reader of this blog, it is highly probable that you are not a serious mathematian :( But there is still hope and so I repeat the most important line of this post that applies to ALL of us ...

You don't need lots of knowledge to have a good idea, just imagination.

But if you are indeed a serious mathematician, or aspire to be one, why not check out Vinay Deolaliker's proof here.

And while we are at it, why don't you overcome your fear of mathematics by visiting this lens: Are You Afraid of Mathematics?

Stumble Upon Toolbar

No comments:

My Library