Vinay Deolalikar, a mathematician who works for HP Labs, claims to
have proven that P is not equal to NP. The problem is the greatest
unsolved problem in theoretical computer science and is one of seven
problems in which the Clay Mathematics Institute has offered million
dollar prizes to the solutions.

The question of whether P equals NP essentially asks whether there
exist problems which take a long time to solve but whose solutions can
be checked quickly. More formally, a problem is said to be in P if there
is a program for a Turing machine, an ideal theoretical computer with
unbounded amounts of memory, such that running instances of the problem
through the program will always answer the question in polynomial time —
time always bounded by some fixed polynomial power of the length of the
input. A problem is said to be in NP, if the problem can be solved in
polynomial time when instead of being run on a Turing machine, it is run
on a non-deterministic Turing machine, which is like a Turing machine
but is able to make copies of itself to try different approaches to the
problem simultaneously.

Mathematicians have long believed that P does not equal NP, and the
question has many practical implications. Much of modern cryptography,
such as the RSA algorithm and the Diffie-Hellman algorithm, rests on
certain problems, such as factoring integers, being in NP and not in P.
If it turned out that P=NP, these methods would not work but many now
difficult problems would likely be easy to solve. If P does not equal NP
then many natural, practical problems such as the traveling salesman
problem are intrinsically difficult.

In 2000, the Clay Foundation listed the “Clay Millenium Problems,”
seven mathematical problems each of which they would offer a million
dollars for a correct solution. One of these problems was whether P
equaled NP. Another of these seven, the PoincarĂ© conjecture, was solved
in 2002 by Grigori Perelman who first made headlines for solving the
problem and then made them again months later for refusing to take the
prize money.

On August 7, mathematician Greg Baker noted on his blog that he had
seen a draft of a claimed proof by Deolalikar although among experts a
draft had apparently been circulating for a few days. Deolalikar’s proof
works by connecting certain ideas in computer science and finite model
theory to ideas in statistical mechanics. The proof works by showing
that if certain problems known to be in NP were also in P then those
problems would have impossible statistical properties. Computer
scientists and mathematicians have expressed a variety of opinions about
Deolalikar’s proof, ranging from guarded optimism to near certainty
that the proof is incorrect. Scott Aaronson of the Massachusetts
Institute of Technology has expressed his pessimism by stating that he
will give $200,000 of his own money to Deolalikar if the proof turns out
to be valid. Others have raised specific technical issues with the
proof but noted that the proof attempt presented interesting new
techniques that might be relevant to computer science whether or not the
proof turns out to be correct. Richard Lipton, a professor of computer
science at Georgia Tech, has said that “the author certainly shows
awareness of the relevant obstacles and command of literature supporting
his arguments.” Lipton has listed four central objections to the proof,
none of which are necessarily fatal but may require more work to
address. On August 11, 2010, Lipton reported that consensus of the
reviewers was best summarized by mathematician Terence Tao, who
expressed the view that Deolalikar’s paper probably did not give a proof
that P!=NP even after major changes, unless substantial new ideas are
added., and the question has many practical implications. Much of modern
cryptography, such as the RSA algorithm and the Diffie-Hellman
algorithm, rests on certain problems, such as factoring integers, being
in NP and not in P. If it turned out that P=NP, these methods would not
work but many now difficult problems would likely be easy to solve. If P
does not equal NP then many natural, practical problems such as the
traveling salesman problem are intrinsically difficult.

In 2000, the Clay Foundation listed the “Clay Millenium Problems,”
seven mathematical problems each of which they would offer a million
dollars for a correct solution. One of these problems was whether P
equaled NP. Another of these seven, the PoincarĂ© conjecture, was solved
in 2002 by Grigori Perelman who first made headlines for solving the
problem and then made them again months later for refusing to take the
prize money.

On August 7, mathematician Greg Baker noted on his blog that he had
seen a draft of a claimed proof by Deolalikar although among experts a
draft had apparently been circulating for a few days. Deolalikar’s proof
works by connecting certain ideas in computer science and finite model
theory to ideas in statistical mechanics. The proof works by showing
that if certain problems known to be in NP were also in P then those
problems would have impossible statistical properties. Computer
scientists and mathematicians have expressed a variety of opinions about
Deolalikar’s proof, ranging from guarded optimism to near certainty
that the proof is incorrect. Scott Aaronson of the Massachusetts
Institute of Technology has expressed his pessimism by stating that he
will give $200,000 of his own money to Deolalikar if the proof turns out
to be valid. Others have raised specific technical issues with the
proof but noted that the proof attempt presented interesting new
techniques that might be relevant to computer science whether or not the
proof turns out to be correct. Richard Lipton, a professor of computer
science at Georgia Tech, has said that “the author certainly shows
awareness of the relevant obstacles and command of literature supporting
his arguments.” Lipton has listed four central objections to the proof,
none of which are necessarily fatal but may require more work to
address. On August 11, 2010, Lipton reported that consensus of the
reviewers was best summarized by mathematician Terence Tao, who
expressed the view that Deolalikar’s paper probably did not give a proof
that P!=NP even after major changes, unless substantial new ideas are
added.

## No comments:

## Post a Comment