Next: 3.1 Highly Constrained SAT Up: Solving Highly Constrained Search Previous: 2 Quantum Computers

# 3 The Satisfiability Problem

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.

Next: 3.1 Highly Constrained SAT Up: Solving Highly Constrained Search Previous: 2 Quantum Computers