P vs NP...or is it Proof vs Non-Proof?
I am sure you have all read about it...In fact, I am sure it was in the headlines of your local newspapers or the lead story on local newscasts this month. Just to be sure, I am talking about the recently announced mathematics discovery by Vinay Deolalikar, a HP computer scientist. In fact, as this is near the start of a new school year, I know all of you shared this discovery and its importance with your students...as an example that new mathematics continues to be created, etc....even over the summer.
What was his claim? That the class of NP problems is not equal to the class of P problems. What does this mean...plus what are the implications?
The possible differentiation of NP and P problems was raised in 1971. It even became one of the seven Millennium Prize Problems, which the Clay Mathematics Institute offers $1,000,000 rewards for viable solutions.
In a nutshell, a P problem can be solved in "polynomial time," while a NP problem requires "nondeterministic polynomial time" (i.e. not any reasonable time and thus is essentially unsolvable). The use of technology does not change the situation.
Now, mathematicians and computer scientists tend to agree that the two classes of problems (P vs. NP) are not equivalent...but no proof has been found....until now. And, despite Deolalikar's offer of both a preliminary 100-page proof now and a firm proof later, the reaction is that his efforts will not suffice. One skeptic, MIT's Scott Aaronson, has even offered an additional reward of $200,000 if Deolalikar's proof is correct. Is this another troublesome episode akin to Wiles proof of Fermat's Last Theorem?