Lower bounds for k-DNF resolution on random 3-CNFs
From MaRDI portal
Publication:3581425
DOI10.1145/1060590.1060628zbMath1192.68307MaRDI QIDQ3581425
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
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, Toward a model for backtracking and dynamic programming, Short propositional refutations for dense random 3CNF formulas, The complexity of the Hajós calculus for planar graphs, On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution