Simplified lower bounds for propositional proofs

DOI10.1305/NDJFL/1040046140MaRDI QIDQ1374208zbMATH OpenOpenAlexFDO

Authors Alasdair Urquhart, Xudong Fu

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

bounded depth propositional proofslower boundspigeonhole principleswitching lemmas

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Exponential lower bounds for the pigeonhole principle
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• The Complexity of Propositional Proofs

Cites work

• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Approximation and Small-Depth Frege Proofs
• Exponential lower bounds for the pigeonhole principle
• Hard examples for resolution
• scientific article; zbMATH DE number 3904558 (Why is no real title available?)
• scientific article; zbMATH DE number 806753 (Why is no real title available?)
• Many hard examples for resolution
• Mathematical logic.
• Parity, circuits, and the polynomial-time hierarchy
• The complexity of the pigeonhole principle

Cited in

(19)

• Bounded-depth Frege complexity of Tseitin formulas for all graphs
• Partially definable forcing and bounded arithmetic
• Random resolution refutations
• LA, permutations, and the Hajós calculus
• Minimum propositional proof length is NP-hard to linearly approximate
• Lower bounds for bounded depth Frege proofs via Pudlák-Buss games
• Lower bounds to the size of constant-depth propositional proofs
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• A Logical Autobiography
• Reflections on Proof Complexity and Counting Principles
• Boolean functions on \(S_n\) which are nearly linear
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity
• On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
• On small-depth frege proofs for \textsf{PHP}
• On bounded depth proofs for Tseitin formulas on the grid; revisited
• Strength and limitations of Sherali-Adams and nullstellensatz proof systems
• Complexity measures on the symmetric group and beyond (extended abstract)
• Uniqueness for 2-intersecting families of permutations and perfect matchings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1374208)