Wednesday, April 01, 2009

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?


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

    You can't just leave us hanging like that.

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

  3. A 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.

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

  4. You had me going!

  5. Thomas Hampson the famous opera singer? Aha...

  6. April 1! :)
    Check Lipton:

  7. Every April 1 on this blog...

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

  9. Wait Luca, weren't you in middle school in 1986? :)

  10. The "1971 incident" in Shaker, Ohio:

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