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

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

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

• 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
• scientific article; zbMATH DE number 2174386 (Why is no real title available?)
• 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

(10)

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

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)