Lower bounds for \(k\)-DNF resolution on random 3-CNFs

DOI10.1007/S00037-011-0026-0zbMath1252.68129OpenAlexW1992239490MaRDI QIDQ430840

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (2)

Special issue in memory of Misha Alekhnovich. Foreword ⋮ Resolution and the binary encoding of combinatorial principles

Cites Work

• Unnamed Item
• Toward a model for backtracking and dynamic programming
• 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
• On the weak pigeonhole principle
• The Efficiency of Resolution and Davis--Putnam Procedures
• Many hard examples for resolution
• 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
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Pseudorandom Generators in Propositional Proof Complexity

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