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

DOI10.1145/1060590.1060628zbMath1192.68307OpenAlexW2007575279MaRDI QIDQ3581425

Michael Alekhnovich

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060628

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, Toward a model for backtracking and dynamic programming, On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution, The complexity of the Hajós calculus for planar graphs, Short propositional refutations for dense random 3CNF formulas