Resolution lower bounds for perfect matching principles

DOI10.1016/j.jcss.2004.01.004zbMath1106.03049OpenAlexW2088421560MaRDI QIDQ1881260

Alexander A. Razborov

Publication date: 4 October 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.01.004

zbMATH Keywords

resolutionproof complexitypigeonhole principle

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items

Width versus size in resolution proofs ⋮ Towards NP-P via proof complexity and search ⋮ Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms ⋮ Resolution lower bounds for the weak functional pigeonhole principle. ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ A combinatorial characterization of resolution width ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Unnamed Item ⋮ The Complexity of Propositional Proofs ⋮ Propositional proof complexity ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ Resolution over linear equations modulo two ⋮ Reflections on Proof Complexity and Counting Principles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for the polynomial calculus
• Resolution lower bounds for the weak functional pigeonhole principle.
• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• Resolution proofs of matching principles
• Resolution lower bounds for the weak pigeonhole principle
• Hard examples for resolution
• Short proofs are narrow—resolution made simple
• Pseudorandom Generators in Propositional Proof Complexity
• Regular resolution lower bounds for the weak pigeonhole principle

This page was built for publication: Resolution lower bounds for perfect matching principles