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.

Feb. 1999