HP Researcher Claims to Crack Compsci Complexity Conundrum

HP Labs principal research scientist Vinay Deolalikar has posted what he claims is a solution to what is widely known as 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$1 million. It is one of only seven problems, collectively known as the Millennium Prize Problems, the institute has offered this bounty for. One of the seven, the Poincaré conjecture, was officially solved in 2006. It is unclear yet if Deolalikar will get the cash, since Clay has not 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.