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

DOI10.1007/S00037-011-0026-0zbMATH Open1252.68129OpenAlexW1992239490MaRDI QIDQ430840FDOQ430840

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

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

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)

Cites Work

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

Cited In (4)

• Resolution and the binary encoding of combinatorial principles
• Proof complexity and the binary encoding of combinatorial principles
• Special issue in memory of Misha Alekhnovich. Foreword
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution

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)