An Exponential Lower Bound for Width-Restricted Clause Learning

DOI10.1007/978-3-642-02777-2_14zbMath1247.68253OpenAlexW1489444259MaRDI QIDQ3637163

Jan Johannsen

Publication date: 7 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02777-2_14

Mathematics Subject Classification ID

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

Related Items (1)

On Linear Resolution

Cites Work

• Unnamed Item
• Near optimal seperation of tree-like and general resolution
• Short proofs for tricky formulas
• Optimality of size-width tradeoffs for resolution
• Short resolution proofs for a sequence of tricky formulas
• Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Pool Resolution and Its Relation to Regular Resolution and DPLL with Clause Learning
• A machine program for theorem-proving

This page was built for publication: An Exponential Lower Bound for Width-Restricted Clause Learning