Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas

DOI10.1007/978-3-642-14186-7_4MaRDI QIDQ4930576zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Jan Johannsen

Publication date 29 September 2010

Published in Theory and Applications of Satisfiability Testing – SAT 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14186-7_4

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• An Exponential Lower Bound for Width-Restricted Clause Learning
• Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
• Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
• scientific article; zbMATH DE number 522871
• Query learning of bounded-width OBDDs
• Query learning of bounded-width OBDDs
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• On the expressive power of CNF formulas of bounded tree- and clique-width
• A stronger LP bound for formula size lower bounds via clique constraints
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

Cited in

(7)

• Limitations of restricted branching in clause learning
• Space complexity in polynomial calculus
• Limitations of Restricted Branching in Clause Learning
• An Exponential Lower Bound for Width-Restricted Clause Learning
• On CDCL-Based Proof Systems with the Ordered Decision Strategy
• Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
• Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution

This page was built for publication: Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas

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