Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR94-018 | 12th December 1994 00:00

#### An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

TR94-018
Authors: Jan Krajicek, Pavel Pudlak, Alan Woods
Publication: 12th December 1994 00:00
Keywords:

Abstract:

We 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.

ISSN 1433-8092 | Imprint