Simplified lower bounds for propositional proofs

DOI10.1305/ndjfl/1040046140zbMath0882.03052OpenAlexW2075146634MaRDI QIDQ1374208

Xudong Fu, Alasdair Urquhart

Publication date: 2 December 1997

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1040046140

zbMATH Keywords

lower boundspigeonhole principleswitching lemmasbounded depth propositional proofs

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (8)

Boolean functions on $S_n$ which are nearly linear ⋮ Partially definable forcing and bounded arithmetic ⋮ Random resolution refutations ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ LA, permutations, and the Hajós calculus ⋮ A Logical Autobiography ⋮ Reflections on Proof Complexity and Counting Principles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for the pigeonhole principle
• The complexity of the pigeonhole principle
• Parity, circuits, and the polynomial-time hierarchy
• Many hard examples for resolution
• Hard examples for resolution
• Approximation and Small-Depth Frege Proofs
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

This page was built for publication: Simplified lower bounds for propositional proofs