Proceedings

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

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2570-2574.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-428

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

Clause learning is a technique used by back-tracking-based propositional satisfiability solvers, where some clauses obtained by analysis of conflicts are added to the formula during backtracking. It has been observed empirically that clause learning does not significantly improve the performance of a solver when restricted to learning clauses of small width only. This experience is supported by lower bound theorems. It is shown that lower bounds on the runtime of width-restricted clause learning follow from lower bounds on the width of resolution proofs. This yields the first lower bounds on width-restricted clause learning for formulas in 3-CNF.

  1. [Alekhnovich et al., 2007] Michael Alekhnovich, Jan Jo- hannsen, Toniann Pitassi, and Alasdair Urquhart. An expo- nential separation between regular and general resolution. Theory of Computing, 3:81-102, 2007.
  2. [Alon and Spencer, 2002] N. Alon and J. Spencer. The Prob- abilistic Method. John Wiley and Sons, 2002.
  3. [Atserias and Dalmau, 2008] Albert Atserias and Victor Dal- mau. A combinatorial characterization of resolution width. Journal of Computer and System Sciences, 74:323-334, 2008.
  4. [Atserias et al., 2009] Albert Atserias, Johannes Klaus Fichte, and Marc Thurley. Clause learning algorithms with many restarts and bounded-width resolution. In Oliver Kullmann, editor, Theory and Practice of Satisfia- bility Testing -SAT 2009, pages 114-127. Springer LNCS 5584, 2009.
  5. [Bayardo Jr. and Schrag, 1997] Roberto J. Bayardo Jr. and Robert C. Schrag. Using CSP look-back techniques to solver real-world SAT instances. In Proc. 14th Natl. Con- ference on Artificial Intelligence, pages 203-208, 1997.
  6. [Beame et al., 2004] Paul Beame, Henry A. Kautz, and Ashish Sabharwal. Towards understanding and harness- ing the potential of clause learning. Journal of Artificial Intelligence Research, 22:319-351, 2004.
  7. [Ben-Sasson and Wigderson, 2001] Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow -resolution made simple. Journal of the ACM, 48:149-169, 2001.
  8. [Bonet and Galesi, 2001] Maria Luisa Bonet and Nicola Galesi. Optimality of size-width tradeoffs for resolution. Computational Complexity, 10(4):261-276, 2001.
  9. [Buss et al., 2008] Samuel R. Buss, Jan Hoffmann, and Jan Johannsen. Resolution trees with lemmas: Resolution re- finements that characterize DLL algorithms with clause learning. Logical Methods in Computer Science, 4(4), 2008.
  10. [Davis et al., 1962] Martin Davis, George Logemann, and Donald W. Loveland. A machine program for theorem- proving. Communications of the ACM, 5(7):394-397, 1962.
  11. [Gomes et al., 1997] Carla P. Gomes, Bart Selman, and Nuno Crato. Heavy-tailed distributions in combinatorial search. In Gert Smolka, editor, Principles and Practice of Constraint Programming -CP97. Springer LNCS 1330, 1997.
  12. [Hertel et al., 2008] Philipp Hertel, Fahiem Bacchus, Toni- ann Pitassi, and Allen van Gelder. Clause learning can effectively p-simulate general propositional resolution. In Dieter Fox and Carla P. Gomes, editors, Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008, pages 283-290. AAAI Press, 2008.
  13. [Hoffmann, 2007] Jan Hoffmann. Resolution proofs and DLL-algorithms with clause learning. Diploma Thesis, LMU München, 2007.
  14. [Iwama and Miyazaki, 1999] Kazuo Iwama and Shuichi Miyazaki. Tree-like resolution is superpolynomially slower than dag-like resolution for the pigeonhole princi- ple. In Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC), pages 133-142, 1999.
  15. [Johannsen, 2009] Jan Johannsen. An exponential lower bound for width-restricted clause learning. In Oliver Kull- mann, editor, Theory and Practice of Satisfiability Testing -SAT 2009, pages 128-140. Springer LNCS 5584, 2009.
  16. [Kolaitis and Vardi, 1995] Phokion G. Kolaitis and Moshe Y. Vardi. On the expressive power of Datalog: Tools and a case study. Journal of Computer and System Sciences, 51(1):110-134, 1995.
  17. [Krishnamurthy, 1985] Balakrishnan Krishnamurthy. Short proofs for tricky formulas. Acta Informatica, 22:253-274, 1985.
  18. [Marques-Silva and Sakallah, 1996] João P. Marques-Silva and Karem A. Sakallah. GRASP -a new search algorithm for satisfiability. In Proc. IEEE/ACM International Con- ference on Computer Aided Design (ICCAD), pages 220- 227, 1996.
  19. [Pipatsrisawat and Darwiche, 2009] Knot Pipatsrisawat and Adnan Darwiche. On the power of clause-learning SAT solvers with restarts. In Proceedings of the 15th Inter- national Conference on Principles and Practice of Con- straint Programming (CP09), pages 654-668, 2009.
  20. [Segerlind et al., 2004] Nathan Segerlind, Samuel R. Buss, and Russell Impagliazzo. A switching lemma for small restrictions and lower bounds for k-DNF resolution. SIAM Journal on Computing, 33(5):1171-1200, 2004.
  21. [Stålmarck, 1996] Gunnar Stålmarck. Short resolution proofs for a sequence of tricky formulas. Acta Informatica, 33:277-280, 1996.
  22. [Tseitin, 1968] G.S. Tseitin. On the complexity of derivation in propositional calculus. Studies in Constructive Mathe- matics and Mathematical Logic, Part 2, pages 115-125, 1968.
  23. [Zhang et al., 2001] Lintao Zhang, Conor F. Madigan, Matthew W. Moskewicz, and Sharad Malik. Efficient con- flict driven learning in a Boolean satisfiability solver. In Proc. IEEE/ACM International Conference on Computer Aided Design (ICCAD), pages 279-285, 2001.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards