Communications of the ACM
Step 1: Post Elusive Proof. Step 2: Watch Fireworks.
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