Archive for December, 2008


December 31, 2008

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.