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.

Feb. 1999