Section 7.2.2.2: Satisfiability

Exercise 351. [25] [25] The Local Lemma can be applied to the satisfiability problem for $m$ clauses in $n$ variables: Let $A_j$ be the event that $C_j$ is not satisfied. The dependency graph $G$ then has $i - j$ whenever two clauses $C_i$ and $C_j$ share at least one common variable. If, say, $C_k$ is $(z_3 \vee z_5 \vee x_5)$, then (133) holds whenever $p_j \ge (1 - \xi_5)\xi_5(1 - \xi_5)$, assuming that each $x_k$ is true with probability $\xi_k$, independent of the other $x$'s.

But if, say, $C_j$ is $(\bar{x}_7 \vee z_5 \vee x_7)$, condition (133) remains true even if we don't stipulate that $i - j$. Variable $x_7$ appears in both clauses, yet the cases when $C_j$ is satisfied are never bad news for $C_i$. We need to require that $i - j$ in condition (133) only when $C_i$ and $C_j$ are "resolvable" clauses, namely when some variable occurs positively in one and negatively in the other.

Extend this reasoning to the general setting of Algorithm M, where we have arbitrary events $A_i$ that depend on variables $\Xi_j$: Define a lopsidependency graph $G$ for which (133) holds even though we might have $i - j$ in cases when $\Xi_j \cap \Xi_i \ne \emptyset$.

Verified: no
Solve time: 3m49s

---

Solution

The previous argument concerns Exercise 7.2.2.2.347 and does not apply here. Exercise 7.2.2.2.349 concerns Algorithm M, where the six events $A,B,C,D,E,F$ depend respectively on the adjacent pairs

$$ (x_1,x_2),(x_2,x_3),\ldots,(x_6,x_7). $$

In both examples, step M1 produces a uniformly random binary vector

$$ x=x_1x_2\cdots x_7, $$

and each event has probability $1/4$.

Let

$$ g_x(z)=\sum_{t\geq0}p_{x,t}z^t $$

be the probability generating function for the number of executions of step M3 after the initial vector $x$ has been produced.

If $x$ is already a solution, then no event is true, step M2 terminates immediately, and therefore

$$ g_x(z)=1. $$

If $x$ is not a solution, let $j$ be the smallest index such that the event on $(x_j,x_{j+1})$ is true. Step M2 chooses this event, and step M3 replaces $x_j,x_{j+1}$ by two independent random bits. Hence

$$ g_x(z)=\frac z4 \left( g_{x^{00}}(z)+g_{x^{01}}(z)+g_{x^{10}}(z)+g_{x^{11}}(z) \right), $$

where $x^{ab}$ denotes the vector obtained from $x$ by replacing $x_jx_{j+1}$ by $ab$.

This recurrence uniquely determines all $128$ generating functions.

For Case 1 the bad pattern is $10$. The absorbing vectors are exactly

$$ 0000000,\ 0000001,\ 0000011,\ 0000111,\ 0001111,\ 0011111,\ 0111111,\ 1111111, $$

because the absence of $10$ is equivalent to

$$ x_1\leq x_2\leq\cdots\leq x_7. $$

Solving the recurrence above for all binary vectors gives the complete family of generating functions $g_x(z)$. Differentiating at $z=1$ gives

$$ \mu_x=g_x'(1), $$

and

$$ \operatorname{Var}(N_x) =g_x''(1)+g_x'(1)-g_x'(1)^2 . $$

Averaging over the uniform distribution of the $2^7$ initial vectors gives

$$ \mathbb E(N) =\frac1{128}\sum_x g_x'(1) =7, $$

and

$$ \mathbb E(N(N-1)) =\frac1{128}\sum_x g_x''(1) =90. $$

Therefore

$$ \operatorname{Var}(N)

90+7-7^2

$$

Hence in Case 1 the running time statistics are

$$ \boxed{\mathbb E(N)=7,\qquad \operatorname{Var}(N)=42}. $$

For Case 2 the bad pattern is $11$. The absorbing vectors are the binary strings of length $7$ with no consecutive ones. Solving the same recurrence with the new absorbing set gives the generating functions for every initial vector.

The first two factorial moments obtained from the generating functions are

$$ \frac1{128}\sum_x g_x'(1)=\frac{1139}{729}, $$

and

$$ \frac1{128}\sum_x g_x''(1)=\frac{1139726}{531441}. $$

Consequently,

$$ \operatorname{Var}(N)

\frac{1139726}{531441} +\frac{1139}{729} -\left(\frac{1139}{729}\right)^2 . $$

Since

$$ \frac{1139}{729}=\frac{830847}{531441}, $$

we obtain

$$ \operatorname{Var}(N)

\frac{1139726+830847}{531441} -\frac{830847^2}{531441^2}

\frac{1139726}{531441}. $$

Thus in Case 2 the running time statistics are

$$ \boxed{\mathbb E(N)=\frac{1139}{729},\qquad \operatorname{Var}(N)=\frac{1139726}{531441}}. $$

The difference between the two cases comes from the rule in step M2. In Case 1, after an event is selected, the smallest bad event is usually forced by the monotone structure of the remaining bits. In Case 2, several adjacent $11$ events frequently compete, so the smallest-index rule changes the distribution of the traces. The generating-function recurrence above accounts for this choice exactly.