Section 7.2.2.2: Satisfiability

Exercise 192. ▶ [HM21] [HM21] Another way to model satisfiability when there are $N$ equally likely clauses is to study $S(p)$, the probability of satisfiability when each clause is independently present with probability $p$.

a) Express $S(p)$ in terms of the numbers $Q_m = \binom{N}{m} q_m$.

b) Assign uniform random numbers in $[0,.,1)$ to each clause; then at time $t$, for $0 \le t \le N$, consider all clauses that have been assigned a number less than $t/N$. (Approximately $t$ clauses will therefore be selected, when $N$ is large.) Show that $S_{k,n} = \int_0^N S_{k,n}(t/N), dt$, the expected amount of time during which the chosen clauses remain satisfiable, is very similar to the satisfiability threshold $S_{k,n}$ of (76).

Verified: no
Solve time: 3m36s

---

Edit

Solution

Let (N) be the total number of possible clauses in the (k)-SAT instance. For (0\leq m\leq N), let (q_m) be the probability that a uniformly chosen set of (m) clauses is satisfiable, and define

[ Q_m=\binom{N}{m}q_m . ]

Thus (Q_m) is the number of satisfiable subsets of clauses having exactly (m) clauses.

(a)

Each clause is independently included with probability (p). A particular subset containing exactly (m) clauses is selected with probability

[ p^m(1-p)^{N-m}. ]

Among the (\binom{N}{m}) subsets of size (m), exactly (Q_m) are satisfiable. Therefore the contribution from all satisfiable formulas with (m) clauses is

[ Q_m p^m(1-p)^{N-m}. ]

The possible clause counts are disjoint cases, so summing over all (m) gives

[ \boxed{ S(p)=\sum_{m=0}^{N}Q_m p^m(1-p)^{N-m}. } ]

For the (k)-SAT model, this is the same satisfiability probability denoted by (S_{k,n}(p)).

(b)

Give each of the (N) possible clauses an independent random label uniformly distributed in ([0,1)). At time (t), with (0\leq t\leq N), select all clauses whose labels are less than

[ \frac{t}{N}. ]

A fixed clause is selected with probability (t/N), independently of the other clauses. Hence the selected formula at time (t) has the same distribution as a random formula in which each clause is independently present with probability

[ p=\frac{t}{N}. ]

Let (I(t)) be the indicator that the selected formula is satisfiable at time (t). The total amount of time for which the evolving formula remains satisfiable is

[ X=\int_0^N I(t),dt . ]

Taking expectations and using linearity of integration gives

\int_0^N \mathbb{E}[I(t)],dt . ]

Since (I(t)) is an indicator variable,

\Pr(I(t)=1)

S_{k,n}\left(\frac{t}{N}\right). ]

Therefore

\int_0^N S_{k,n}\left(\frac{t}{N}\right),dt . } ]

It remains to compare this expectation with the threshold (S_{k,n}) defined in (76). The satisfiability probability is monotone decreasing in the number of clauses. Adding clauses can only remove satisfying assignments, so if (m_1<m_2), then

[ q_{m_1}\geq q_{m_2}. ]

Consequently (S_{k,n}(t/N)) is a decreasing function of (t). The threshold (S_{k,n}) is the value of the clause count at which this decreasing function changes from being close to (1) to being close to (0).

For a threshold function with a narrow transition region, the area under the curve is essentially the location of the transition. To see this, suppose that for some small (\varepsilon>0) the probability satisfies

[ S_{k,n}(t/N)\geq 1-\varepsilon ]

for (t\leq S_{k,n}-w), and

[ S_{k,n}(t/N)\leq \varepsilon ]

for (t\geq S_{k,n}+w). Splitting the integral into the three intervals before, during, and after the transition gives

\int_0^{S_{k,n}-w}S_{k,n}\left(\frac{t}{N}\right),dt + \int_{S_{k,n}-w}^{S_{k,n}+w}S_{k,n}\left(\frac{t}{N}\right),dt + \int_{S_{k,n}+w}^{N}S_{k,n}\left(\frac{t}{N}\right),dt . ]

The first integral differs from (S_{k,n}-w) by at most (\varepsilon(S_{k,n}-w)). The last integral is at most (\varepsilon(N-S_{k,n}-w)). The middle integral has length (2w) and its value is bounded between (0) and (2w). Hence the total difference between the integral and (S_{k,n}) is controlled by the transition width and the small error (\varepsilon).

Thus, when the satisfiability curve has a sharp threshold, the expected amount of time for which a random ordering of clauses remains satisfiable satisfies

[ \boxed{ \int_0^N S_{k,n}\left(\frac{t}{N}\right),dt \approx S_{k,n}. } ]

The two quantities describe the same threshold phenomenon: one locates the transition by the clause count at which satisfiability disappears, while the other measures the expected stopping time in a random process that reveals clauses gradually.