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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: