By Tech Powered Dad | August 15, 2010
In an age where we are surrounded by computers that solve problems of almost unimaginable complexity in a matter of seconds, students of math may be surprised to learn that there is an entire category of problems generally believed to be “unsolvable” by computers. The class of P problems can be solved in “polynomial time,” while NP problems are solved in “nondeterministic polynomial time.” At the risk of oversimplifying, P problems can be solved by a computer fairly quickly. NP problems have so many possible solutions that it’s believed that computers simply will never be fast enough to solve in an amount of time useful to human beings.
In other words, it is believed that P and NP are not equal and fundamentally different. Even though their differences are pretty much universally accepted, no one has been able to prove that they are not equal, and yet, we all depend on it. Today, many encryption methods used to keep credit card numbers and other secure information safe depend on the fact that it would take a computer solution of an NP problem in order to break them.
A solution that proves P is not equal to NP has eluded mathematicians since the question was first posed in 1971, and it is considered such an important and intriguing idea that it was named to the list of Millennium Prize Problems. This is a list of unsolved seven problems that the Clay Mathematics Institute announced an a award $1,000,000 to a mathematician who could solve any of them. As of this article, only one of the problems had been solved.
Within the last week, an HP computer scientist, Vinay Deolalikar, published his proof that P was not equal to NP. Tech Powered Math held off a few days to gauge the reaction from the mathematical community. It has been fairly unanimous and harsh. In the age of blogs and Twitter, many mathematicians took to the internet to criticize the proof. Scott Aaronson of MIT actually was so skeptical of the proof that he offered an additional $200,000 to Deolakilar if his proof turns out to be correct.
Deolalikar says this was a preliminary version of his proof, and the final version will be forthcoming. Will it address the concerns that the mathematical community has with his work? Stay tuned. TPM will keep you updated.