Does SAT always have short analytic proofs?
It is known that proofs of the unsatisfiability of pigeonhole problems must be at least length $2^{n^\epsilon}$ when the resolution proof system is used.  $\epsilon$ depends on the difference between the number of pigeons and the number of holes, but $\epsilon &gt; 0$ always.