All reports by Author Alan Woods:

__
TR94-018
| 12th December 1994
__

Jan Krajicek, Pavel Pudlak, Alan Woods#### An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

Jan Krajicek, Pavel Pudlak, Alan Woods

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