- Image by jurvetson via Flickr
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.
In 2000 the Clay Mathematics Institute picked seven of the greatest unsolved problems in the field, named them “Millennium Problems” and offered $1 million for the solution of each of them. P versus NP is one of those problems. (In March, the first prize was awarded to a reclusive Russian mathematician, Grigory Perelman, for the solution to the century-old Poincaré conjecture. A few months later he refused the prize.)
P versus NP has enormous practical and economic importance, because modern cryptography is based on the assumption, which is workable so far, that P does not equal NP. In other words, there are problems that are impossible for computers to solve, but for which the solutions are easily recognizable. If these problems were shown to be solvable, that could undermine modern cryptography, which could paralyze electronic commerce and digital privacy because transactions would no longer be secure.
In a note sent to a small group of researchers on Aug. 6, Dr. Deolalikar wrote: “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.”
