Blog: HP Researcher Claims to Crack Compsci Complexity Conundrum

HP Researcher Claims to Crack Compsci Complexity Conundrum
IDG News Service (08/09/10) Jackson, Joab

Hewlett-Packard researcher Vinay Deolalikar claims to have solved the computer science problem widely known as P versus NP. In an email to a group of math professors, Deolalikar said he was announcing proof that polynomial time (P) is not equal to nondeterministic polynomial time (NP), which may mean certain problems can only be solved by brute force searching, if solutions can be found at all. Deolalikar said he pieced together 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. No one who is familiar with the problem has said Deolalikar has solved it thus far, considering the amount of checking that needs to be done on his solution. The Clay Mathematics Institute has promised to pay $1 million to the person who solves the problem. The P versus NP problem involves "determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure," according to the institute.

View Full Article