✦ LIBER ✦

How good are branching rules in DPLL?

✍ Scribed by Ming Ouyang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 346 KB
Volume: 89
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(98)00045-6

No coin nor oath required. For personal study only.

✦ Synopsis

The Davis-Putnam-LogemannLoveland algorithm is one of the most popular algorithms for solving the satisfiability problem.

Its efficiency depends on its choice of a branching rule. We construct a sequence of instances of the satisfiability problem that fools a variety of "sensible" branching rules in the following sense: when the instance has n variables, each of the "sensible" branching rules brings about 62(2"5) recursive calls of the Davis-Putnam-Logemanll-Loveland algorithm, even though only 0( I ) such calls are necessary.

📜 SIMILAR VOLUMES

Learning to Select Branching Rules in th

Learning to Select Branching Rules in the DPLL Procedure for Satisfiability

✍ Michail G. Lagoudakis; Michael L. Littman 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 199 KB

The DPLL procedure is the most popular complete satisfiability (SAT) solver. While its worst case complexity is exponential, the actual running time is greatly affected by the ordering of branch variables during the search. Several branching rules have been proposed, but none is the best in all case

How good are the Electrodes we use in PE

How good are the Electrodes we use in PEFC?

✍ M. Eikerling; A.S. Ioselevich; A.A. Kornyshev 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 955 KB

## Abstract Basically, companies and laboratories implement production methods for their electrodes on the basis of experience, technical capabilities and commercial preferences. But how does one know whether they have ended up with the best possible electrode for the components used? What should b

Randomized controlled trials in neurosur

Randomized controlled trials in neurosurgery—how good are we?

✍ K. Schöller; S. Licht; J.-C. Tonn; E. Uhl 📂 Article 📅 2009 🏛 Springer Vienna 🌐 English ⚖ 175 KB

Mate choice when males are in patches: o

Mate choice when males are in patches: optimal strategies and good rules of thumb

✍ John M.C. Hutchinson; Konrad Halupka 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 512 KB

How you can tell if the simulations in c

How you can tell if the simulations in computational criminology are any good

✍ Richard Berk 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 375 KB

Going Up–Going Down: How Good Are People

Going Up–Going Down: How Good Are People at Forecasting Trends and Changes in Trends?

✍ MARCUS O'CONNOR; WILLIAM REMUS; KEN GRIGGS 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

Prior studies of judgemental time-series forecasting have found that people have problems with downward-sloping series. This laboratory-based study presents a controlled experiment of series direction and it investigates the problems of changing trends. Results con®rm that people have signi®cant dic