EUVIMEDEUVIMED entdecken
Crossref

Formula Caching in DPLL

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

ACM Transactions on Computation Theory · 2010

DOI: 10.1145/1714450.1714452 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2010. Verfasst von Paul Beame und 3 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 28 Literaturangaben. Gefördert von: Division of Mathematical Sciences, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization , in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability by several authors. We formalize these methods by developing extensions of the fruitful connection that has previously been developed between DPLL algorithms for satisfiability and tree-like resolution proofs of unsatisfiability. We analyze a number of variants of these formula caching methods and characterize their strength in terms of proof systems. These proof systems are new and simple, and have a rich structure. We compare them to several studied proof systems: tree-like resolution, regular resolution, general resolution, Res(k), and Frege systems and present both simulation and separations. One of our most interesting results is the introduction of a natural and implementable form of DPLL with caching, FCW reason . This system is surprisingly powerful: we prove that it can polynomially simulate regular resolution, and furthermore, it can produce short proofs of some formulas that require exponential-size resolution proofs.

Förderung

  • Division of Mathematical Sciences
  • National Science Foundation

Zitieren

APA

Beame, P., Impagliazzo, R., Pitassi, T., & Segerlind, N. (2010). Formula Caching in DPLL. ACM Transactions on Computation Theory. https://doi.org/10.1145/1714450.1714452

Vancouver

Beame P, Impagliazzo R, Pitassi T, Segerlind N. Formula Caching in DPLL. ACM Transactions on Computation Theory. 2010. doi:10.1145/1714450.1714452

BibTeX
@article{Beame2010,
  author = {Beame, Paul and Impagliazzo, Russell and Pitassi, Toniann and Segerlind, Nathan},
  title = {Formula Caching in DPLL},
  journal = {ACM Transactions on Computation Theory},
  year = {2010},
  doi = {10.1145/1714450.1714452}
}
Kostenlos starten →