next up previous
Next: 6 Solving Maximally Constrained Up: Solving Highly Constrained Search Previous: 4.5.4 Required Search Time

5 Applying the Algorithm to k-SAT 

The algorithm presented above is effective for 1-SAT by exploiting the simple structure of such problems. As described in §3, many highly constrained k-SAT problems have a similar structure. This observation allows the 1-SAT algorithm to be applied to more general problems, although with a reduction in performance. Specifically, applying Eq. (13) requires knowing the number of conflicts the assignments would have in the corresponding maximally constrained 1-SAT problem whose solution is equal to one of the solutions of the original k-SAT problem. As described in §3.1, for the most part this can be computed efficiently using the neighborhood relations for the problem. This suggests simply changing the 1-SAT algorithm to use tex2html_wrap_inline2506 .

To see how this approximation changes the performance, consider an assignment s with y bad values with respect to a specific solution r and let

equation560

The vector tex2html_wrap_inline2514 used with the k-SAT problem is related to the vector from the corresponding 1-SAT problem tex2html_wrap_inline2518 by tex2html_wrap_inline2520 . Except for this change, the remaining transformations of the algorithm are the same as in the 1-SAT case. Thus

displaymath567

where tex2html_wrap_inline2522 is the result of the corresponding 1-SAT problem, i.e., all amplitude in the solution, and tex2html_wrap_inline2524 is a diagonal matrix, with elements given by tex2html_wrap_inline2526 . It is convenient to define the average value of tex2html_wrap_inline2526 over all assignments with y bad values:

equation571

where the sum is restricted to just the tex2html_wrap_inline2532 assignments with y bad values.

The change in the amplitude in the solution state is determined by tex2html_wrap_inline2536 when r is the solution. This change can be expressed using Eq. (17) by recalling that h=0 for the solution and replacing the phases tex2html_wrap_inline2542 by the error in the phases, tex2html_wrap_inline2544 :

  equation577

Since all the tex2html_wrap_inline2542 have unit magnitude, tex2html_wrap_inline2548 . If the problem has only one solution, the probability the algorithm will find it is tex2html_wrap_inline2550 . If there are multiple solutions, this is a lower bound on the probability.

The following sections use these observations to extend the range of problems to which the 1-SAT algorithm can be effectively applied.


next up previous
Next: 6 Solving Maximally Constrained Up: Solving Highly Constrained Search Previous: 4.5.4 Required Search Time

Tad Hogg
Feb. 1999