a Give a randomized algorithm and estimate its expected time

(a) Give a randomized algorithm and estimate its expected time.

(b) Give a deterministic algorithm. Argue about its correctness using the method of conditional expectations.

Hint:

Randomized algorithm: What about assigning boolean values randomly to boolean variables? What is the expected number of satisfied clauses? After assigning boolean values randomly to boolean variables: count satisfied clauses. Iterate again, as long as needed.

Deterministic algorithm: Consider boolean variables one by one. For a given variable p, count how many clauses, that have not been made true yet, are made true by setting p true, and how many by setting p false. Then act greedily.

Solution

Given a Boolean formula in CNF, determine, whether is satisfiable or not.!

Ex: AND of clauses

(A1 V A2 V A3 V A4) (1 V 3 V 4) (A1 V 2 V 3 )

Each clause has at least one literal set to true.

If 1= true, A2 = true then

Clause 1 and 2 are satisfiable but the Clause 3 requires A3 literal set to be false for it to be a satisfiable

Input : A Boolean formula in conjunctive normal form with exactly two distinct literals in every clause. E.g., = (x1 V~x2) ^ (x1 V ~x3) ^ (~x1 V x3) ^ (~x1 V ~x2)

1)/* Start with an arbitrary initial assignment to the literals*/

for (i = 0; i < m; i++)   {xi = true;} Let us call this assignment A

2)/* here function number_satisfied() returns the number of satisfied clauses for the current assignment */

for (t = 0; t < T && number_satisfied(x, n) < n; t++) {

select an arbitrary non-satisfied clause CJ;

randomly and uniformly pick one of the literals xi in CJ ;

    xi = (xi + 1) mod 2; }

3) If (number_satisfied(x, n) == n) { report that the set of clauses is satisfiable ;}

else{    report that the set of clauses is not satisfiable}

Randomized 2-SAT Analysis

Distance can never be larger than n

if it starts at some 0 < i < n

Dominated by a walk where

With probability exactly ½ distance to A is reduced

With probability exactly ½ distance to A is increased

Let us define a random variable Xi

Xi=# of steps to reach state n starting from state i

Xi=1 + # of steps to reach state n starting from state i+1 with probably ½ (Xi+1)

Xi=1 + # of steps to reach state n starting from state i-1 with probably ½ ( Xi-1)

this is a memory less property There for start from the current state is a fresh start.

E[Xi]=1/2 E[1+Xi+1]+1/2E[1+ Xi-1]

= 1+(E[ Xi-1 ]+E[Xi+1])/2

Let Si=E[ Xi ] Then

Si=1+( Si-1+Si+1)/2

Sn-1=1+( Sn-2 + Sn)/2

S0=S1+1                                               ............(1)

2S1=S0+S2+2     .............................(2)

2Sn-1=Sn-2+2..............................(n)

adding equations 1 to n we get

Sn-1=2(n-1)+1=2n-1

Sn-2=(2n-1)+(2n-3)

S0=(2n-1)+(2n-3)+..............+3+1=n2

De randomization : First devise a randomized algorithm then argue that it can be derandomized to yield a deterministic algorithm

Consider the following formula.

(A1 V 2 V A3) ( 2 V 3 V A1) ( 3 V A2 V 1 )

The assignment for the literals in the above clauses can be drawn in the form of a binary tree.

Here, starting from the root, first compute the average at each node. Then pick the path having greater average.

The process for computing the average is

Consider the root assignment A1=0, A1 = 1

if A1 = 1 , compute the satisfiable clauses probability.

i.e. (A1 V 2 V A3)   ... satisfied.

      ( 2 V 3 V A1) ... satisfied

      ( 3 V A2 V      1 ) ... not satisfied. ->

   By discarding 1 from the clause we obtain (   A2 V 3 ).

The probability that this clause is not satisfied is 1/4. So the probabilitythat this clause is satisfied is ¾ . Thus the total probability turns out to be (1 + 1 + ¾) =1+1/4. This is the average when A1 = 1

Similarly compute the average for A1 = 0. which comes out to be 10/4.

Choose the greater average and move towards that path. So we move towards A1 = 1 path.

Now compute the average by taking the assignment A2=0 and A2=1 and move towards the path with greater average.

Thus at each level i, we have to compute the average, with assignment true, and with false.

Thus, on reaching the leaf, we would have the average number of clauses which will be satisfiable with the assignment on the chosen path.

In the above algorithm greedy approach is been followed, at each level we check which sub tree will give the best average & we take decision according to the current maximum. Thus algorithm may result in an sub-optimal result.