[FOM] P NP buzz
friedman at math.ohio-state.edu
Tue Aug 10 01:31:53 EDT 2010
The author Vinay Deolalikar works at Hewlett Packard and seems to have
strong credentials. The paper reads like that written carefully by a
serious expert. It is being seized upon immediately by the huge crowd
of directly interested parties, who are vastly closer to this kind of
thing than I am, and so I am just going to watch this drama unfold.
I never seriously worked on this problem, since with all of its
notoriety, I thought it likely that any successful effort would take
anyone at least 10 years of full time effort, with a large probability
of getting nothing. At my age, I don't have the time for such an
adventure, given such poor prospects for success. In addition, the
consensus, which I agree with, is that P not= NP is obviously true,
and almost nobody would regard this result as surprising. However, I
do expect that if it is correct, then it can be used to obtain some
important things that we don't already "know".
So there are two competing "obvious" points of view at this early stage.
1. It must be correct. This guy has serious credentials, and so how
can he circulate this paper without having checked it very carefully
with at least some of his coworkers? He certainly knows how
unfortunate it would be to stir up the International community in this
area with a claim to have proved something so notorious that people
can get huge reputations for extremely weak partial results.
2. It must be incorrect. The list of people who have made major
efforts on this problem reads like the who's who of theoretical
computer science. They work full time in the field - many of these
luminaries for many decades. Almost all of them admit to having given
up hope, and just try for extremely weak partial results. They only
rarely get even these. Vinay says he did this on his own independently
of full time Hewlett Packard duties, and mentions about 2 years of
There seems to be emerging, a place of record for this matter. Look at
and watch the drama unfold.
I am particularly watching "Harrison" at the end of the current
instantiation of the site. This might have come in after the beginning
comments on the site. I think I know who "Harrison" is, although there
may be more than one.
More information about the FOM