Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis

DOI10.1016/j.ipl.2015.09.013zbMath1346.68100OpenAlexW2150412474WikidataQ61732565 ScholiaQ61732565MaRDI QIDQ894453

Ilario Bonacina, Navid Talebanfard

Publication date: 1 December 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.09.013

zbMATH Keywords

resolutiontheory of computationproof complexitystrong exponential time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (2)

Strong ETH and resolution via games and the multiplicity of strategies ⋮ Unnamed Item

Cites Work

• A characterization of tree-like resolution size
• On converting CNF to DNF
• An improved exponential-time algorithm for k -SAT
• Short proofs are narrow—resolution made simple
• Strong ETH holds for regular resolution
• Exponential Lower Bounds for the PPSZ k-SAT Algorithm
• On the complexity of \(k\)-SAT
• Unnamed Item

This page was built for publication: Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis