The Letter

Richard Lipton posts about the naming of the P=NP problem, the only Millennium Prize problem not named after people. But Lipton skipped an important part of the story.

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.

So is the Gödel letter a complete fabrication? Or is it this post?