next up previous
Next: 7.2 Balanced Clauses Up: 7 Solving Highly Constrained Previous: 7 Solving Highly Constrained

7.1 Random k-SAT

For random k-SAT with prespecified solution, Stirling's asymptotic expansion in Eq. (8) shows that tex2html_wrap_inline2656 for y=O(n) when m grows as tex2html_wrap_inline2662 , which is much less that the maximum tex2html_wrap_inline2664 . In this case, the asymptotic behavior of the bound B is determined by the values near the maximum of the binomial coefficient, i.e., near y=n/2. Thus if tex2html_wrap_inline2670 , we have tex2html_wrap_inline2672 . From Eq. (29), tex2html_wrap_inline2674 at least when B< 1. This is the case for tex2html_wrap_inline2678 where


where tex2html_wrap_inline2684 . For instance, tex2html_wrap_inline2686 is 1.01 and 17.3 for k=2 and 3, respectively. Thus, the algorithm presented here is simple enough to allow an analytic bound on its behavior for highly constrained problems, thus demonstrating its asymptotic effectiveness in these cases. Other, more complex, structured quantum algorithms have only been evaluated empirically [29, 30], which is limited to small problems.

The algorithm's behavior with fewer constraints, i.e., tex2html_wrap_inline2690 , is not easily evaluted analytically since the bound provided by B is no longer useful. Instead, the behavior can be examined empirically using a classical simulation [34], which is however limited to problems with a relatively small number of variables. These empirical studies may eventually be extendable to larger problems using approximate evaluation techniques [9].

An example is given in Fig. 3. This shows good performance for highly constrained problems, as expected from the behavior of the lower bound. Performance is also good with few constraints; not because the algorithm is capturing the problem structure particularly well but rather because there are many solutions to weakly constrained problems. As with other classical and quantum search methods that use problem structure, the hardest cases are for problems with an intermediate number of constraints [32].

Figure 3: Probability to find a solution for random 3-SAT for n=10 (solid) and 20 (dashed) vs. m/n, on a log-log scale. Each point is an average over at least 100 problem instances, and includes error bars for the standard deviation in this estimate of the averge. The error bars are smaller than the size of the plotted points. The gray lines show the corresponding lower bounds tex2html_wrap_inline1596 .

From Fig. 4 we see that the nonzero asymptotic limit for the probability of a solution appears to continue for somewhat fewer constraints than expected from the value of tex2html_wrap_inline2686 . Below this value, the probability for finding a solution appears to decrease as a power of n, indicated by linear scaling on the log-log plot of Fig. 4 for tex2html_wrap_inline2704 . Similar empirical evaluations of the scaling with an intermediate number of constraints where the hard problems are concentrated, e.g., m = 4 n for 3-SAT, shows linear scaling on a log-plot, indicating exponential decrease in the probability to find a solution. Moreover, the resulting search costs in these cases are larger than those of other structured quantum search algorithms [29, 30]. Thus the structure of these harder cases differs enough from the simple 1-SAT problems that this algorithm is not effective for them.

Figure 4: Probability to find a solution for random soluble 3-SAT vs. n with, from top to bottom, tex2html_wrap_inline1600 , tex2html_wrap_inline1602 and tex2html_wrap_inline1604 , respectively, on a log-log plot. For each value of n, at least 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.

In summary, the algorithm solves highly constrained problems with tex2html_wrap_inline2670 in O(1) steps for tex2html_wrap_inline2678 , and possibly for somewhat smaller values of tex2html_wrap_inline2724 as well. As the number of clauses is further reduced, the required number of steps appears to grow polynomially when tex2html_wrap_inline2726 and exponentially when m = O(n).

next up previous
Next: 7.2 Balanced Clauses Up: 7 Solving Highly Constrained Previous: 7 Solving Highly Constrained

Tad Hogg
Feb. 1999