NP search problems have exponentially many possible states and a
procedure that quickly checks whether a given state is a
solution [23]. Constraint satisfaction problems
(CSPs) [41] are an example. A CSP consists of
n variables, 
, and the requirement to assign a
value to each variable to satisfy given constraints. An
assignment specifies a value for each
variable.
One important CSP is the satisfiability problem (SAT), which consists
of a logical propositional formula in n variables and the
requirement to find a value (true or false) for each variable that
makes the formula true. This problem has 
assignments. For
k-SAT, the formula consists of a conjunction of clauses and each
clause is a disjunction of k variables, any of which may be
negated. For 
these problems are NP-complete. An example of
such a clause for k=3, with the third variable negated, is 
OR
OR (NOT 
), which is false for exactly one assignment for
these variables: 
. A clause with k variables is false for exactly one
assignment to those variables, and true for the other 
choices.
Since the formula is a conjunction of clauses, a solution must satisfy
every clause. We say an assignment conflicts with a particular clause
when the values the assignment gives to the variables in the clause
make the clause false. For example, in a four variable problem, the
assignment
conflicts with the k=3 clause given above, while
does not. Thus each clause is a constraint that adds one conflict to all assignments that conflict with it. The number of distinct clauses m is then the number of constraints in the problem.
The assignments for SAT can also be viewed as bit strings with the
correspondence that the 
bit is 0 or 1 according to whether
is assigned the value false or true, respectively. In turn,
these bit strings are the binary representation of integers, ranging
from 0 to 
. For definiteness, we arbitrarily order the bits so
that the values of and 
correspond, respectively, to the
least and most significant bits of the integer. For example, the
assignment
corresponds to the integer whose binary representation is 0100, i.e., the number 4.
For bit strings r and s, let | s | be the number of 1-bits in
s and 
the bitwise AND operation on r and s. Thus
counts the number of 1-bits both assignments have
in common. We also use d(r,s) as the Hamming distance between r
and s, i.e., the number of positions at which they have different
values. These quantities are related by
An example 1-SAT problem with n=2 is the propositional formula (NOT
) AND (NOT ). This problem has a unique solution: 
, an assignment with the bit representation
00. The remaining assignments for this problem have bit
representations 01, 10, and 11.
