Menu
HP researcher claims to crack compsci complexity conundrum

HP researcher claims to crack compsci complexity conundrum

A Hewlett-Packard researcher puts forth a possible solution to a tough computer science puzzler

While Hewlett-Packard reels from the fallout of its CEO Mark Hurd stepping down, the company can bask in the glory of at least one potentially positive accomplishment: An HP researcher has offered up what he says is a solution to one of the hardest problems in computer science.

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.

"I am pleased to announce a proof that P is not equal to NP," Deolalikar announced in an e-mail to a group of math professors, which was then posted on Sunday 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 the problem, 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 claimed 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 characterization of NP," wrote Scott Aaronson, an assistant professor of electrical engineering and computer science at Massachusetts Institute of Technology, in a noncommittal 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.

Joab Jackson covers enterprise software and general technology breaking news for The IDG News Service. Follow Joab on Twitter at @Joab_Jackson. Joab's e-mail address is Joab_Jackson@idg.com


Follow Us

Join the newsletter!

Or

Sign up to gain exclusive access to email subscriptions, event invitations, competitions, giveaways, and much more.

Membership is free, and your security and privacy remain protected. View our privacy policy before signing up.

Error: Please check your email address.

Tags Hewlett-Packardpopular science

Featured

Slideshows

Leading female front runners of the Kiwi ICT industry honoured at 2019 WIICTA

Leading female front runners of the Kiwi ICT industry honoured at 2019 WIICTA

Reseller News has honoured the leading female front runners of the New Zealand ICT industry at the 2019 Women in ICT Awards (WIICTA) in Auckland. The awards recognised standout individuals across six categories, spanning Entrepreneur, Rising Star, Shining Star, Community, Technical and Achievement. Photos by Gino Demeer.

Leading female front runners of the Kiwi ICT industry honoured at 2019 WIICTA
Reseller News kicks off awards season in 2019 with Judges' Lunch

Reseller News kicks off awards season in 2019 with Judges' Lunch

The 2019 Reseller News Innovation Awards has kicked off with the Judges Lunch in Auckland with 70 judges in the voting panel. The awards will reflect the changing dynamics of the channel, recognising excellence across customer value and innovation - spanning start-ups, partners, distributors and vendors. Photos by Christine Wong.

Reseller News kicks off awards season in 2019 with Judges' Lunch
Reseller News welcomes industry figures for 2019 Hall of Fame lunch

Reseller News welcomes industry figures for 2019 Hall of Fame lunch

Reseller News welcomed 2018 inductees - Chris Simpson, Kendra Ross and Phill Patton - to the third running of the Reseller News Hall of Fame lunch, held at the French Cafe in Auckland. The inductees discussed the changing landscape of the technology industry in New Zealand, while outlining ways to attract a new breed of players to the ecosystem. Photos by Gino Demeer.

Reseller News welcomes industry figures for 2019 Hall of Fame lunch
Show Comments