Lower bounds for k-DNF resolution on random 3-CNFs

DOI10.1007/S00037-011-0026-0MaRDI QIDQ430840zbMATH OpenOpenAlexFDO

Authors Michael Alekhnovich

Publication date 26 June 2012

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-011-0026-0

zbMATH Keywords

propositional proof complexityrandom CNFs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in computer science (03B70) Complexity of proofs (03F20)

Recommendations

• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• scientific article; zbMATH DE number 1775444
• Random resolution refutations
• Refuting random 3CNF formulas in propositional logic
• Short propositional refutations for dense random 3CNF formulas

Cites work

• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• Many hard examples for resolution
• On the weak pigeonhole principle
• Pseudorandom Generators in Propositional Proof Complexity
• Relations between average case complexity and approximation complexity
• Sharp thresholds of graph properties, and the $k$-sat problem
• Short proofs are narrow—resolution made simple
• The efficiency of resolution and Davis-Putnam procedures
• Toward a model for backtracking and dynamic programming

Cited in

(8)

• Special issue in memory of Misha Alekhnovich. Foreword
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis
• Proof complexity and the binary encoding of combinatorial principles
• Strong ETH holds for regular resolution
• A note about \(k\)-DNF resolution
• Random resolution refutations
• Resolution and the binary encoding of combinatorial principles

This page was built for publication: Lower bounds for \(k\)-DNF resolution on random 3-CNFs

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