  A method to calculate the average size of Davis-Putnam-Loveland-Logemann
(DPLL) search trees for random computational problems is introduced, and
applied to the satisfiability of random CNF formulas (SAT) and the coloring of
random graph (COL) problems. We establish recursion relations for the
generating functions of the average numbers of (variable or color) assignments
at a given height in the search tree, which allow us to derive the asymptotics
of the expected DPLL tree size, 2^{N w + o(N)}, where N is the instance size. w
is calculated as a function of the input distribution parameters (ratio of
clauses per variable for SAT, average vertex degree for COL), and the branching
heuristics.
