Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.

Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi

Browse the full MFCS paper archive.