In general, SAT problems are difficult to solve. However, in a few simple cases the very regular structure of the search space allows much more effective algorithms. One example is given by 1-SAT problems. In this case, each clause eliminates one value for a single variable allowing classical algorithms to examine the variables independently, giving an overall search cost of O(n) in spite of the exponentially large number of assignments. A 1-SAT problem has a solution if and only if each of the m clauses involves a distinct variable. Otherwise, both values for some variable will be in conflict, i.e., making a clause false, resulting in no solutions.
This simple structure allows for rapid search. SAT problems with larger clauses have a more complicated structure. Nevertheless, when the k-SAT problems are highly constrained, their structure is close to that of 1-SAT. To see this, consider a soluble k-SAT problem. With respect to a particular solution of that problem, define the good value for each variable as the value (true or false) it is assigned in that solution, while the opposite value is the bad one for that variable. For k-SAT problems with many constraints, the number of bad values in an assignment can usually be determined rapidly from its number of conflicts, even though determining exactly which variables have incorrect assigned values requires first finding the solution. In such cases, using the number of bad values results in a tractable algorithm as long as a priori knowledge of the solution is not assumed.
For example, consider soluble problems with the largest possible
number of constraints. For k-SAT, these maximally constrained
soluble problems have 
where
i.e., the single solution precludes any clause that conflicts with it.
An assignment with j bad values contains 
sets of k
variables all of which have the same values as the solution. Each of
the remaining sets conflicts with at least one clause in the
problem. Thus each assignment with j bad values has
conflicts. This quantity grows strictly monotonically with j for 
, so in these cases j is directly determined by the number
of conflicts. Assignments with 
are not
distinguishable.
Assignments with j=n-k+1 can also be corrrectly determined by
including neighborhood information. To see this, consider an
assignment s with j bad values, and its n neighbors, i.e.,
assignments at Hamming distance one from s. Of these neighbors, j
have j-1 bad values, and the remaining n-j have j+1 bad
values. For , s has j neighbors with fewer conflicts
and n-j with more. Thus for these assignments, examining the number
of conflicts in the neighbors readily determines the value of
j. When j=n-k+1, the assignment continues to have j neighbors
with fewer conflicts, but now the remaining k-1 neighbors have the
same number of conflicts since the additional bad value does not
increase the number of conflicts. Finally, the neighbors of
assignments with 
all have the same number of
conflicts. Thus examining the number of conflicts in an assignment's
neighbors determines the value of j, with the exception that
assignments with are not distinguishable.
The value of j is the number of conflicts that s would have in the maximally constrained 1-SAT problem with the same solution as the given maximally constrained k-SAT problem. Thus for a maximally constrained k-SAT problem let
The value of 
can be determined rapidly, in much the
same way that a classical local search method checks the number of
conflicts among neighbors of its current state to determine which
assignment to move to next [42, 47]. Thus 
is a computationally tractable approximation to the number of
conflicts each assignment would have in the corresponding 1-SAT
problem. Except for a few assignments with many conflicts, gives the correct value. Specifically, only assignments with
at least n-k+3 bad values are given an incorrect value of j by this
approximation. In particular, the approximation is completely correct
for k=2.
While classical searches use the number of conflicts in an assignment
and its neighbors, another possibility for maximally constrained
problems is to use the number of conflicts in the assignment and
its complement (i.e., the assignment with opposite values for all
the variables). If the assignment has j bad values, its complement
will have n-j. As described above, the number of conflicts in an
assignment uniquely determines the corresponding value of j provided
. On the other hand, the number of conflicts in the
complement assignment uniquely determines j when 
, or
. Thus, as long as n;SPMgt;2k, at least one of these conditions
will be true for all 
and the correct value of j
can be determined.
