[FOM] P NP buzz

[Harvey Friedman]

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  
effort.

There seems to be emerging, a place of record for this matter. Look at

http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that- 
p≠np/

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.

Harvey Friedman