ECCC-Report TR94-018https://eccc.weizmann.ac.il/report/1994/018Comments and Revisions published for TR94-018en-usMon, 12 Dec 1994 00:00:00 +0200
Paper TR94-018
| An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle |
Jan Krajicek,
Pavel Pudlak,
Alan Woods
https://eccc.weizmann.ac.il/report/1994/018We prove lower bounds of the form $exp\left(n^{\epsilon_d}\right),$
$\epsilon_d>0,$ on the length of proofs of an explicit sequence of
tautologies, based on the Pigeonhole Principle, in proof systems
using formulas of depth $d,$ for any constant $d.$ This is the
largest lower bound for the strongest proof system, for which any
superpolynomial lower bounds are known.
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/018