next up previous
Next: 4.4 Performance of the Up: 4 Solving 1-SAT Previous: 4.2 The Algorithm for

4.3 Examples

To illustrate the algorithm, consider the example problem in §3. It has n=m=2. With the assignments ordered according to the corresponding interger value, i.e., 00, 01, 10, and 11, tex2html_wrap_inline2130 where

  equation296

The resulting behavior is:

tabular302

giving an amplitude of 1 in the solution assignment 00.

Another example, with n=m=3 is the propositional formula (NOT tex2html_wrap_inline1708 ) AND (NOT tex2html_wrap_inline1710 ) AND tex2html_wrap_inline1712 , with assignments tex2html_wrap_inline2172 , represented as bit vectors, and solution tex2html_wrap_inline1714 , i.e., the bit vector 100. In this case U can be expressed in terms of tex2html_wrap_inline2178 from Eq. (15) in block form:

equation311

For this case, the algorithm's behavior is:

tabular320

Again, all the amplitude is in the solution.



Tad Hogg
Feb. 1999