acm-header
Sign In

Communications of the ACM

ACM News

Step 1: Post Elusive Proof. Step 2: Watch Fireworks.


View as: Print Mobile App Share:

The potential of Internet-based collaboration was vividly demonstrated this month when complexity theorists used blogs and wikis to pounce on a claimed proof for one of the most profound and difficult problems facing mathematicians and computer scientists.

Vinay Deolalikar, a mathematician and electrical engineer at Hewlett-Packard, posted a proposed proof of what is known as the “P versus NP” problem on a Web site, and quietly notified a number of the key researchers in a field of study that focuses on problems that are solvable only with the application of immense amounts of computing power.

The researcher asserted that he had demonstrated that P (the set of problems that can be easily solved) does not equal NP (those problems that are difficult to solve, but easy to verify once a solution is found). As with earlier grand math challenges—for example, Fermat’s last theorem—there is a lot at stake, not the least of which is a $1 million prize.

From The New York Times
View Full Article


 

No entries found