A great post by Gil Kalai on the importance (or at least coolness) of mathematical results about impossibility.

Of course, one can frame pretty much any mathematical result as an impossibility statement. Math theorems are generally of the form *a implies b*, which can be read as *it’s impossible to have a and not b*. That said, the real impossibility results are like obscenity; I know them when I see them.

One minor bone of contention: Kalai invokes the P vs. NP problem needlessly, as (e.g.) the time hierarchy theorems are more than sufficient. Of course, there really are important problems that aren’t computable using standard models, such as the famous Post Correspondence Problem.

### Like this:

Like Loading...

This entry was posted on December 31, 2008 at 4:43 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply