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

DOI10.1016/J.IPL.2015.09.013MaRDI QIDQ894453zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

resolutionproof complexitytheory of computationstrong 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)

Recommendations

• Strong ETH holds for regular resolution
• Lower bounds for k-DNF resolution on random 3-CNFs
• On the complexity of \(k\)-SAT
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Narrow proofs may be maximally long

Cites work

• scientific article; zbMATH DE number 1445296 (Why is no real title available?)
• A characterization of tree-like resolution size
• An improved exponential-time algorithm for k -SAT
• Exponential lower bounds for the PPSZ \(k\)-SAT algorithm
• On converting CNF to DNF
• On the complexity of \(k\)-SAT
• Short proofs are narrow—resolution made simple
• Strong ETH holds for regular resolution

Cited in

(7)

• Strong ETH and resolution via games and the multiplicity of strategies
• scientific article; zbMATH DE number 7471677 (Why is no real title available?)
• Strong ETH holds for regular resolution
• On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
• Conditional lower bounds for failed literals and related techniques
• Strong ETH and resolution via games and the multiplicity of strategies
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894453)