Exponential Average Time for the Pure Literal Rule
Khaled M. Bugrara, Youfang Pan, Paul Walton Purdom · SIAM Journal on Computing · 1989
This paper gives exponential lower bounds for the average time of an algorithm based on a simplified version of the pure literal rule from the Davis–Putnam procedure. It is shown that this algorithm requires an average time that is exponential in v, the number of variables, when p, the probability that a literal is in a clause, is proportional to $1/v$ and t, the number of clauses in the predicate, is at least a linear function of v. The time is greater than any polynomial in v over a somewhat larger range of parameters. For the two cases $t = \Theta (\ln v)$ and $p = O(\ln v/v^{3/2} )$, the results of this lower-bound analysis are the same (to within a constant factor) as the upper-bound results in [SIAM J. Comput., 14 (1985), pp. 943–953]. The results of this and other papers show that the fastest analyzed algorithm for random satisfiability problems depends on the parameters of the distribution. Backtracking, the pure literal rule, and the new algorithm of Iwama [Report KSU/ICS 88-01, Institute of Computer Science, Kayoto Sangyo University, Kyoto, Japan, 1988 each have a large region of parameter setting where it is exponentially faster than the other two.