Sign In

Communications of the ACM

ACM News

Crowdsourcing Peer Review

View as: Print Mobile App Share:

It is the greatest question in computer science. A negative answer would likely give a fundamentally deeper understanding of the nature of computation. And a positive answer would transform our world: Computers would acquire mind-boggling powers such as near-perfect translation, speech recognition and object identification; the hardest questions in mathematics would melt like butter under computation’s power; and current computer security methods would be as easy to crack as a TSA-approved suitcase lock.

So when Vinay Deolalikar, a computer scientist at Hewlett Packard labs in India, sent an email on August 7 to a few top researchers claiming that P doesn’t equal NP—thereby answering this question in the negative and staking a claim on the million-dollar Millennium Prize offered by the Clay Mathematics Institute—it sent shock waves through the community. Usually, computer scientists groan when they find such a claim in their Inbox, expecting the typical amateurish "proof" with the same hoary errors. But Deolalikar is a recognized and published scientist, and his paper had novel ideas from promising areas of research.

The paper spurred an intense, open, Internet-based effort to understand it and pursue its ideas, attracting such luminaries as Fields Medalists Terry Tao and Timothy Gowers. The examination uncovered deep flaws that are probably irremediable—but has also helped spur on a new model of research.

From ScienceNews
View Full Article


No entries found