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.
