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 .

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

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

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

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

The change in the amplitude in the solution state is determined by 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 by the error in the phases, :

Since all the have unit magnitude, . If the problem has only one solution, the probability the algorithm will find it is . 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: 6 Solving Maximally Constrained Up: Solving Highly Constrained Search Previous: 4.5.4 Required Search Time