next up previous
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, tex2html_wrap_inline1694 , 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 tex2html_wrap_inline1698 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 tex2html_wrap_inline1704 these problems are NP-complete. An example of such a clause for k=3, with the third variable negated, is tex2html_wrap_inline1708 OR tex2html_wrap_inline1710 OR (NOT tex2html_wrap_inline1712 ), which is false for exactly one assignment for these variables: tex2html_wrap_inline1714 . A clause with k variables is false for exactly one assignment to those variables, and true for the other tex2html_wrap_inline1718 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 tex2html_wrap_inline1728 bit is 0 or 1 according to whether tex2html_wrap_inline1730 is assigned the value false or true, respectively. In turn, these bit strings are the binary representation of integers, ranging from 0 to tex2html_wrap_inline1732 . For definiteness, we arbitrarily order the bits so that the values of tex2html_wrap_inline1708 and tex2html_wrap_inline1736 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 tex2html_wrap_inline1748 the bitwise AND operation on r and s. Thus tex2html_wrap_inline1754 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 tex2html_wrap_inline1708 ) AND (NOT tex2html_wrap_inline1710 ). This problem has a unique solution: tex2html_wrap_inline1768 , an assignment with the bit representation 00. The remaining assignments for this problem have bit representations 01, 10, and 11.

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

Tad Hogg
Feb. 1999