Loading jsMath...
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: 2610
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