4 ms·

Gödel’s Lost Letter and P=NP

57 points by robg 16y ago

Cushman 16y ago
I like the personal touch you see in these old letters. It'd be nice to see more technical blog posts/comments these days that open with a paragraph asking after the recipient's health, and close with sincere best wishes and congratulations for a recent success.
- thwarted 16y ago
  That would only make the use of TL;DR more appropriate. Blog posts are rarely targeted at an individual, and those that are are often written in a confrontational or sarcastic tone.
  - Cushman 16y ago
    That's a fair point-- and exactly what I'm talking about. This idea that it's a waste of time to write or read anything nice about someone else is a cancer on our community.
    - thwarted 16y ago
      Considering the quality of the average blog post, this would only serve to decrease the signal to noise ratio, especially when what is actually the meat of many posts are already so devoid of useful content. I notice that you didn't start your response with concern about my health nor wished me well on my future endeavors in your sign off.
      - cgs1019 16y ago
        This thread seems possessed of an almost Gödelian self-referentiality.
- sukuriant 16y ago
  This is a personal letter between two people, though, and responses took days. Sending memos back and forth (in a sense what we're doing now), would be wasteful, likely rude, and expensive. For those of you with family in the military, do y'all send long messages to one another, sometimes going at great length to ask a question in the middle of them, like this email? Why?
DiabloD3 16y ago
So, how does this prove (or disprove) N=NP?
jfb 16y ago
I liked this very much. A letter between two of the towering intellects of the modern age that is still so accessible and packed with information puts all those fucking content-free PowerPoint info sinks right in their goddamned place. I also appreciated that it wasn't walled off in scribd or something. I was able to, you know, read the text in a relaxing and "natural" manner.
thisisnotmyname 16y ago
This sounds to me like what we now call the Busy Beaver problem. http://en.wikipedia.org/wiki/Busy_beaver http://en.wikipedia.org/wiki/Busy_beaver
- bdr 16y ago
  It's not. Godel is asking, what's the fastest program that can tell if a (first order predicate logic) formula is provable? Maybe you were confused by the 'max', but what he's doing is defining the complexity of the prover by the hardest (max computational time) formula instance for each length n. You still try to handle that maximum difficulty case as efficiently as possible, it just happens to take the longest.
ctkrohn 16y ago
For what it's worth, Lipton writes an excellent blog. It had very good coverage of the Deolalikar P=NP question, and continues to be interested even to those of us without a theoretical computer science background. Well worth adding to your RSS.

57 points by robg 16y ago

I like the personal touch you see in these old letters. It'd be nice to see more technical blog posts/comments these days that open with a paragraph asking after the recipient's health, and close with sincere best wishes and congratulations for a recent success.

thwarted 16y ago
That would only make the use of TL;DR more appropriate. Blog posts are rarely targeted at an individual, and those that are are often written in a confrontational or sarcastic tone.
- Cushman 16y ago
  That's a fair point-- and exactly what I'm talking about. This idea that it's a waste of time to write or read anything nice about someone else is a cancer on our community.
  - thwarted 16y ago
    Considering the quality of the average blog post, this would only serve to decrease the signal to noise ratio, especially when what is actually the meat of many posts are already so devoid of useful content. I notice that you didn't start your response with concern about my health nor wished me well on my future endeavors in your sign off.
    - cgs1019 16y ago
      This thread seems possessed of an almost Gödelian self-referentiality.
sukuriant 16y ago
This is a personal letter between two people, though, and responses took days. Sending memos back and forth (in a sense what we're doing now), would be wasteful, likely rude, and expensive. For those of you with family in the military, do y'all send long messages to one another, sometimes going at great length to ask a question in the middle of them, like this email? Why?

DiabloD3 16y ago

So, how does this prove (or disprove) N=NP?

jfb 16y ago

I liked this very much. A letter between two of the towering intellects of the modern age that is still so accessible and packed with information puts all those fucking content-free PowerPoint info sinks right in their goddamned place. I also appreciated that it wasn't walled off in scribd or something. I was able to, you know, read the text in a relaxing and "natural" manner.

thisisnotmyname 16y ago

This sounds to me like what we now call the Busy Beaver problem. http://en.wikipedia.org/wiki/Busy_beaver http://en.wikipedia.org/wiki/Busy_beaver

bdr 16y ago
It's not. Godel is asking, what's the fastest program that can tell if a (first order predicate logic) formula is provable? Maybe you were confused by the 'max', but what he's doing is defining the complexity of the prover by the hardest (max computational time) formula instance for each length n. You still try to handle that maximum difficulty case as efficiently as possible, it just happens to take the longest.

ctkrohn 16y ago

For what it's worth, Lipton writes an excellent blog. It had very good coverage of the Deolalikar P=NP question, and continues to be interested even to those of us without a theoretical computer science background. Well worth adding to your RSS.