Hard random 3-SAT problems and the Davis-Putnam procedure

摘要

It is by now well known that randomly generated 3-SAT problems are very difficult to solve on the average when the ratio of clauses to variables is a constant which is approximately equal to 4.24. This difficulty appears to be algorithm-independent, but it is certainly a consequence of using the popular Davis-Putnam procedure in Loveland's form (DPL). The purpose of this paper is to try to provide an explanation of why these problems are hard for DPL by experimentally determining how their complexity decreases as the depth of their associated search trees increases. We use a highly optimized version of DPL to plot the average number of remaining variables versus search tree depth for several nontrivial sizes of critically constrained, underconstrained, and overconstrained problems. These plots have a distinct piecewise-linear shape, consisting of an initial, gradual descent from the original number of variables, and a second, steeper descent to substantially smaller subproblems. They help explain exactly why DPL performs poorly on the critically constrained problems, and why its performance is much better on under- and overconstrained problems. Also, we can use the key parameters of these plots, e.g., the depth at which rapid constraint propagation occurs, as another basis of comparison for implementations of DPL.