Next: 8 Discussion Up: 7 Solving Highly Constrained Previous: 7.1 Random k-SAT

## 7.2 Balanced Clauses

In a similar way, the behavior of problems with balanced clauses can be evaluated, as shown in Fig. 5. In this case the lower bound is much looser than for random soluble problems. This is because, unlike the previous case, significant errors are made in assigning for the large number of assignments with about n/2 bad values. The bound assumes that any such mistake gives the maximum possible contribution to Eq. (27), but in fact because of the limited phase choices in Eq. (13), some such mistakes will nevertheless give the correct value of the phase. Again, the intermediate problems are the most difficult for this algorithm.

Figure 5: Probability to find a solution for random balanced 3-SAT for n=10 (solid) and 20 (dashed) vs. m/n, on a log-log scale. Each point represents 100 problem instances and includes error bars which, in most cases, are smaller than the size of the plotted points. The gray lines show the corresponding lower bounds

Because the bound is so poor, its asymptotic behavior does not offer a useful guide to the behavior of the algorithm for highly constrained problems. Instead, the scaling for is illustrated in Fig. 6. The behavior is consistent with a polynomial decrease in the probability to find a solution, but definitive statements cannot be made from such small problem sizes.

Figure 6: Probability to find a solution for random balanced 3-SAT vs. n with, from top to bottom, and , respectively, on a log-log plot. For each value of n, 100 problem instances were used. Error bars showing the expected error in the estimate are included but are smaller than the size of the plotted points.