Key points are not available for this paper at this time.
Formulas are given for the expected number of nodes in the backtrack tree that is generated while searching for all the solutions of a random predicate. The most general formulas apply to selection from any set of predicates that obeys the following conditions. Each predicate is the conjunction of t terms selected from a set of terms T. For any subset T' T, the probability that the predicate contains only terms from T' depends only on the size of T'. The set T must remain unchanged if each variable xᵢ is replaced by pᵢ (xᵢ), where pᵢ is a permutation function. The time needed to evaluate the general formulas is proportional to v, the number of variables in the predicate. More detailed consideration is given to predicates whose terms are random disjunctive clauses with s literals, t = v^ for some 1 < < s, and the random selections are done with repetition. For this case the expected number of nodes is O (v^ (s -) / (s - 1) ). (Complete enumeration results in O (v) nodes. ) Thus the average time for backtracking in this model is exponential with a sublinear exponent.
Brown et al. (Sat,) studied this question.