Resolution lower bounds for the weak pigeonhole principle
From MaRDI portal
Publication:5501187
DOI10.1145/972639.972640zbMath1317.03036OpenAlexW2039982637MaRDI QIDQ5501187
Publication date: 1 August 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/972639.972640
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (13)
Width versus size in resolution proofs ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ A combinatorial characterization of resolution width ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Unnamed Item ⋮ The Complexity of Propositional Proofs ⋮ Satisfiability via Smooth Pictures ⋮ Propositional proof complexity ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs
This page was built for publication: Resolution lower bounds for the weak pigeonhole principle
