A Hewlett Packard researcher has found what he says is a solution to one of the most difficult problems in computer science.
HP Labs principal research scientist Vinay Deolalikar has posted what he claims is a solution to the P versus NP problem.
So intractable is this problem that the Clay Mathematics Institute has vowed to award the person who solves it US$1million. It is one of only seven problems the institute has offered this bounty for.
It is unclear yet if Deolalikar will get the cash, since Clay has not yet said that it considers the problem solved.
This problem, "one of the outstanding problems in computer science," involves "determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure," an Institute page explains. In the problem, P stands for polynomial time and NP stands for nondeterministic polynomial time.
"I am pleased to announce a proof that P is not equal to NP," Deolalikar announced in an email to a group of math professors, which was then posted last week by Greg Baker, a senior lecturer at the British Columbia Simon Fraser University.
In a nutshell, this may mean that certain problems can only be solved by brute force searching, if solutions can be found at all.
"The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens," Deolalikar wrote.
Naturally, those knowledgeable with the problem hesitate to proclaim that Deolalikar has solved it, given the amount of checking that would need to be done. And while they praise Deolalikar for his thorough approach, one that differs from the more haphazard guesses that are usually presented, no one has definitively acknowledged he has cracked the problem.
"It seems to introduce some thought-provoking new ideas, particularly a connection between statistical physics and the first-order logic characterisation of NP," wrote Scott Aaronson, an assistant professor of electrical engineering and computer science at Massachusetts Institute of Technology, in a blog entry.
"I do not know what to think right now, but I am certainly hopeful," wrote Dick Lipton, a professor of computer science at the Georgia Institute of Technology.