Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




TR94-018
Authors: Jan Krajicek, Pavel Pudlak, Alan Woods
Publication: 12th December 1994 00:00
Downloads: 2467
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