Next: 7 Solving Highly Constrained Up: Solving Highly Constrained Search Previous: 5 Applying the Algorithm

6 Solving Maximally Constrained k-SAT

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.

Next: 7 Solving Highly Constrained Up: Solving Highly Constrained Search Previous: 5 Applying the Algorithm