[FOM] Who released Deolalikar's proof into the wild?

Henry Cohn Henry.Cohn at microsoft.com
Sun Aug 15 20:56:12 EDT 2010

>Sending a paper to 22 people is quite different from making a public 

His e-mail began "I am pleased to announce a proof that P is not equal to NP,
which is attached in 10pt and 12pt fonts" and contains no indication that he
considered the proof tentative or in need of further checking, or that it
should not be distributed.  It reads to me like a public announcement, and
I would have interpreted it that way if I had been one of the recipients.
It's true that Deolalikar was not the first person to post the paper on the web,
but if he envisioned a period of semi-private review by experts before he
made a public announcement, he really didn't communicate that wish clearly.


-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of Richard Heck
Sent: Sunday, August 15, 2010 4:49 PM
To: Foundations of Mathematics
Subject: Re: [FOM] Who released Deolalikar's proof into the wild?

So I said:

> And, unless I am mistaken, Deolalikar is not the one who released the
> purported proof into the wild. That seems worth remembering.
and then Alasdair Urquhart said:

> Deolalikar sent his manuscript to 22 very distinguished
> researchers.  Neither the manuscript nor the covering
> note swore the recipients to secrecy, so the purported proof
> was very rapidly disseminated.
> Under these circumstances, I believe that Vinay
> Deolalikar "released the purported proof into the wild."
and Harvey Friedman said:
> This is not the case. Here is the email that Deolalikar sent around on 
> August 6 that started everything, without the attachments. It is 
> followed below by an email from Steve Cook, one of the receipients, 
> and the originator of the problem, not Galois as Martin Davis implies, 
> which apparently was sent rather widely. I received it a bit down the 
> food chain - not directly from Steve.
So now I say:

I could possibly be wrong about one fact, but, unless I am, I have to 
disagree with both of you. Perhaps the phrase "into the wild" misled. 
It's a common phrase in internet security---one speaks of a virus or 
other sort of exploit being found "in the wild", i.e., out in 
public---and it was in that sense that I was using it.

Sending a paper to 22 people is quite different from making a public 
announcement. What on earth would you have the man do? He thinks he's 
proved (or might have proved) P <> NP, and it's not like he's some 
quack. He's published serious work in serious journals, including prior 
work on similar topics. I think sending the paper out for comment, via 
email, is about as sensible a thing as one could do. Maybe 22 seems a 
bit heavy, but surely we're not supposed to count here. And maybe the 
details weren't as worked out as they should have been. I don't know. 
It's not my area. But I'm definitely with Harvey as far as the low 
standard for what seems to count as a proof these days is concerned.

Maybe Deolalikar would have gone on to make a public announcement, but 
he wasn't the one who did so. He posted the paper on his website *after* 
its existence had been made public. That is when the internet phenomenon 
starts. I can't quite tell if Harvey means to blame Cook for that or 
not. If so, then he agrees with me---not about blaming Cook (I don't 
have a view on that) but about not blaming Deolalikar.

Frankly, I feel bad for the guy. As Harvey said elsewhere, we've all 
been in this kind of position. Either that, or we're not reaching far 
enough. Fortunately, in my case, it's usually only a few people who know 
about it, and my mistakes haven't come in such grand attempts. But I do 
well remember once sending a proof to a handful of people, because I 
thought I'd proved something and couldn't believe it was true. Lucky for 
me, it actually was.

Richard Heck

FOM mailing list
FOM at cs.nyu.edu

More information about the FOM mailing list