Simplified Lower Bounds for Propositional Proofs
Open Access
- 1 October 1996
- journal article
- Published by Duke University Press in Notre Dame Journal of Formal Logic
- Vol. 37 (4), 523-544
- https://doi.org/10.1305/ndjfl/1040046140
Abstract
No abstract availableThis publication has 11 references indexed in Scilit:
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principleRandom Structures & Algorithms, 1995
- Bounded Arithmetic and Lower Bounds in Boolean ComplexityPublished by Springer Science and Business Media LLC ,1995
- Exponential lower bounds for the pigeonhole principlecomputational complexity, 1993
- Approximation and Small-Depth Frege ProofsSIAM Journal on Computing, 1992
- Many hard examples for resolutionJournal of the ACM, 1988
- The complexity of the pigeonhole principlePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Hard examples for resolutionJournal of the ACM, 1987
- Parity, circuits, and the polynomial-time hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- On the Complexity of Derivation in Propositional CalculusPublished by Springer Science and Business Media LLC ,1970
- Zur Hilbertschen BeweistheorieMathematische Zeitschrift, 1927