Impossible

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.

About these ads

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: