Algorithms For Dummies

Solving 2-SAT using randomization

No matter the electronic circuit you have to test using a Boolean representation, 

you  can  render  it  as  a  vector  of  Boolean  variables.  You  can  also  create  another 

FIGURE 18-4: 

Symbols and 

truth tables of 

logic operators 

AND

, 

OR

, and 

NOT

.

---

350

 

   

  PART 5 

 Challenging Difficult Problems

vector to contain the clauses, the set of conditions the circuit needs to satisfy (for 

example, that wire A and wire B should both be 

True

). This isn’t the only way to 

represent  the  problem;  in  fact,  there  are  other  solutions  involving  the  use  of 

graphs. However, for this example, these two vectors are enough.

You solve the problem using a randomized local search in polynomial time. Pro-

fessor Christos H. Papadimitriou, teaching at the University of California at Berke-

ley (

https://people.eecs.berkeley.edu/~christos/

), devised this algorithm, 

called  RandomWalkSAT.  He  presented  it  in  his  paper  “On  Selecting  a  Satisfying 

Truth Assignment,” published in 1991 on the Proceedings of the 32nd IEEE Sym-

posium  on  the  Foundations  of  Computer  Science.  The  algorithm  is  competitive 

when compared to more reasoned ways, and it is an exemplary local search 

approach because it makes just one change at a time on the current solution. It 

uses two nested loops, one for trying the starting solution multiple times and one 

for randomly amending the initial random solution. Repeat the outer loop 

log

2

(k)

 

times (where k is the number of wires). The inner loop uses the following steps:

1. 

Pick a random problem solution.

2. 

Repeat the following steps 

2*k

2

 times:

a.  Determine whether the current solution is the right one. When it is the 

correct solution, break free of all the loops and report the solution.

b.  Pick an unsatisfied clause at random. Choose one of the conditions in it at 

random and amend it.