Gödel’s Lost Letter and P=NP | Hacker News Reader

Gödel’s Lost Letter and P=NP

rjlipton.wordpress.com

57 pointsrobg10 comments

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.

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.

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.

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.

This thread seems possessed of an almost Gödelian self-referentiality.

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?

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.

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

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.

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.

Reply on news.ycombinator.com