  DPLL algorithm for solving the Boolean satisfiability problem (SAT) can be
represented in the form of a procedure that, using heuristics $A$ and $B$,
select the variable $x$ from the input formula $\varphi$ and the value $b$ and
runs recursively on the formulas $\varphi[x := b]$ and $\varphi[x := 1 - b]$.
Exponential lower bounds on the running time of DPLL algorithms on
unsatisfiable formulas follow from the lower bounds for tree-like resolution
proofs. Lower bounds on satisfiable formulas are also known for some classes of
DPLL algorithms such as "myopic" and "drunken" algorithms.
  All lower bounds are made for the classes of DPLL algorithms that limit
heuristics access to the formula. In this paper we consider DPLL algorithms
with heuristics that have unlimited access to the formula but use small memory.
We show that for any pair of heuristics with small memory there exists a family
of satisfiable formulas $\Phi_n$ such that a DPLL algorithm that uses these
heuristics runs in exponential time on the formulas $\Phi_n$.
