If pigs could whistle, then horses could fly

Sometimes a result in Complexity Theory is described (or disparaged?) with the phrase, "If pigs could whistle, then horses could fly". (I can't figure out how this got started; the earliest online example I could find was from Dan Spielman's lecture notes but I'm pretty sure I heard it well before this. Can someone antedate this reference?)

The meaning is that the result is of the form "(something probably false) implies (something probably false)". An example is the Karp-Lipton Theorem:

$NP \subseteq P/poly \Rightarrow$ the Hierarchy collapses.

If you really believe "$NP \subseteq P/poly$" is false, then in some sense the statement is vacuous. If you somehow intuitively feel that "the Hierarchy collapses" is even more probably false than "$NP \subseteq P/poly$" then the statement has value; its contrapositive is that "assuming the Hierarchy doesn't collapse" (which you strongly believe), $NP$ does not have polynomial-size circuits (which maybe you believed less)?

In this particular case, I don't know what your intuition is, but I suppose mine is that I feel $NP \subseteq P/poly$ is more false-seeming than that the Hierarchy collapse. So does the Karp-Lipton tell me anything?! Or is it just, "If pigs could whistle, then horses could fly"?


In this case, the theorem is very meaningful -- but for another reason. As Scott Aaronson once wrote in a blog comment on this subject, "It gives one of the few known bridges between [TM-based complexity classes] and [circuits] -- and thereby lets us prove interesting circuit lower bounds." By this he means the fact that $\Sigma_2$ does not have polynomial-size circuits -- Problem 4c on your homework!