Resolution lower bounds for the weak pigeonhole principle
From MaRDI portal
Publication:5501187
DOI10.1145/972639.972640zbMath1317.03036MaRDI 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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
An Introduction to Lower Bounds on Resolution Proof Systems, The Complexity of Propositional Proofs, LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE, \texttt{SymChaff}: Exploiting symmetry in a structure-aware satisfiability solver, Feasibly constructive proofs of succinct weak circuit lower bounds, Width versus size in resolution proofs, A combinatorial characterization of resolution width, Satisfiability via Smooth Pictures