Potential math challenge solution greeted with skepticism
Norbert Blum, a computer science professor at the University of Bonn, has proposed a solution to an unsolved math problem that could win him $1m, not to mention professional accolades, if his approach withstands scrutiny.
The problem is known as P ≠ NP. It’s one of The Clay Mathematics Institute’s seven Millennium Prize Problems, each of which is associated with a similarly hefty prize.
In layman’s terms, P (polynomial time) refers to problems that are easy for a computer to solve and NP (nondeterministic polynomial time) refers to problems that cannot easily be solved by a computer but are easy for a computer to verify.
The institute’s website provides an example of an NP problem:
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice.
It would be straightforward to write code to check if a suggested list of placements conformed with the housing requirements, but it would be exceedingly difficult to create a program that could, using today’s technology, compute all possible valid permutations.
Proving P≠NP would establish that there are, in fact, a class of problems that are harder to compute than to verify. The alternative would mean we just haven’t identified a fast computational solution.
This isn’t purely an abstract issue. Current cryptography assumes P≠NP; if that turns out to be wrong, online security could become much more of a challenge.
Scott Aaronson, a computer science professor at the University of Texas in Austin, has his doubts. In a blog post on Tuesday, he declined to repeat a past show of skepticism – offering in 2010 to augment the prize with an additional $200,000 if a proof proposed by Vinay Deolalikar of HP Labs wasn’t refuted, which it was. Nonetheless, he suggested flaws will be identified and others have ventured similar doubts.
Luca Trevisan, professor of computer science at UC Berkeley, has identified some of the potential issues that need to be explored, but stops short of offering a conclusion.
If past failures point to future results, then the odds are against Blum’s proof. So far, there have been more than 100 attempts to prove either that P≠NP or that P=NP. Not one has succeeded.
The Register asked Blum in an email whether he was aware of anyone who had identified flaws in his proposed proof or whether anyone has managed to confirm it.
« It is too early for such a question, » said Blum. ®
