The regular structure of maximally constrained soluble *k*-SAT
problems allows them to be solved in *O*(1) steps. That is, the
probability to find a solution remains *O*(1) as *n* increases. Thus
a solution is very likely to be found by repeating the algorithm
*O*(1) times, and, as described above, each trial of the algorithm
involves only one evaluation of the conflicts. To see this, we use
from Eq. (7). For *k*;*SPMgt*;2, this approximation
results in incorrect phase choices for only a few, high-conflict
assignments. Because the proportion of incorrect phases is small, we
can expect this approximation will introduce only small amplitudes in
nonsolution states. However, it will also make the algorithm
incomplete: it can find a solution if one exists but not prove no
solutions exist.

Specifically, can be nonzero only for , where
*y* is the number of bad values in assignment *s*. Thus using
Eq. (27), and Eq. (14),

When , the sum over binomial coefficients can be bounded [46] to give

Thus the probability to obtain a solution is

which rapidly approaches 1. Hence, this algorithm is able to find the
solution in *O*(1) search steps as *n* increases. This behavior is
illustrated in Fig. 1.

**Figure 1:** Behavior of vs. *n* for maximally constrained soluble *k*-SAT for *k*=3 (black) and 4 (gray). For comparison, the bounds from Eq. (28) are shown as the dashed lines.

Similarly, soluble balanced *k*-SAT problems with the maximum possible
number of clauses, given by Eq. (10), give good performance
as shown in Fig. 2. The behavior in this case is
rather irregular and continues for larger values of *n*,
but still gives a high probability to find a
solution. For odd *k*, the probability for a solution is exactly one
for many values of *n*. In fact, by including neighborhood
information, the errors in the remaining cases can also be eliminated,
giving a perfect algorithm for these problems. For even *k*, the
balanced clauses force the problem to have two solutions with opposite
values. Even though this problem structure differs significantly from
that of a 1-SAT problem with a single solution, the algorithm is able
to find solutions for *k*=4 with probability of about 1/2, even as *n*
increases.

**Figure 2:** Behavior of vs. *n* for maximally constrained balanced soluble *k*-SAT for *k*=3 (black) and 4 (gray). For comparison, the bounds based on Eq. (27) are shown as the dashed lines, and is quite small for the *k*=4 case.

Feb. 1999