As I started graduate school in 1985, there was a movement to use the term the

*Cook-Levin Conjecture*instead of P≠NP. There were some who thought this disregarded the important work of Karp, leading to a rather nasty incident at FOCS '86 in Toronto.But when the Gödel letter to von Neumann came to light in 1988 no one knew exactly who to credit the conjecture. Since then people just talk about the P vs. NP problem.

But was the Gödel letter actually written by Gödel? The letter mentions von Neumann's illness. von Neumann kept secret the fact that he had what was then highly experimental chemotherapy treatment even from his closest friends. It's extremely unlikely that Gödel would have known about this treatment at the time he supposedly wrote the letter.

And then there is a curious discussion from a dinner I went to during a STACS conference in the late 90's. I was having dinner with a small group including Thomas Hampson, then at Karlsruhe, and his wife Suzanne. Hampson had done a postdoc with Karp at Berkeley and they wrote several papers together. Hampson also was an expert on Gödel, having given a well-received survey of Gödel's work at a previous STACS.

Suzanne was a museum curator who also occasionally worked with the German version of the FBI on forgeries. I asked her, jokingly, whether she had tried to forge anything herself. She smiled and said "Well there was the letter by G..." At this point Thomas said something short to her in German and Suzanne quickly changed the topic.

"...leading to a rather nasty incident at FOCS '86 in Toronto."

ReplyDeleteYou can't just leave us hanging like that.

I first contemplated the question of P-vs-NP. Since I do not wish to identify myself, it should be known from this point forward as the Anonymous Hypothesis.

ReplyDeleteA point in favor of forgery: The letter seems to be a bit too obvious a demonstration that Goedel thought of P vs NP: throw in the mental work of a mathematician and don't forget the primality of numbers.

ReplyDeleteBut it's a strange April Fools' joke, isn't it?

You had me going!

ReplyDeleteThomas Hampson the famous opera singer? Aha...

ReplyDeleteApril 1! :)

ReplyDeleteCheck Lipton:

http://rjlipton.wordpress.com/2009/04/01/a-new-factoring-algorithm/

Every April 1 on this blog...

ReplyDeleteI thought we had all agreed never to mention the infamous FOCS'86 incident again.

ReplyDeleteWait Luca, weren't you in middle school in 1986? :)

ReplyDeleteThe "1971 incident" in Shaker, Ohio:

ReplyDeletehttp://en.wikipedia.org/wiki/NP-complete#Background

And an independent discovery of P vs NP (Jack Edmonds):

http://www.lamsade.dauphine.fr/~poc/spip.php?article22