next up previous
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 tex2html_wrap_inline1852 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.

   figure1008
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 tex2html_wrap_inline1596

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 tex2html_wrap_inline2650 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.

   figure1014
Figure 6: Probability to find a solution for random balanced 3-SAT vs. n with, from top to bottom, tex2html_wrap_inline1616 and tex2html_wrap_inline1604 , 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.



Tad Hogg
Feb. 1999