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.
