TAOCP 7.2.2.2 Exercise 213

Section 7.2.2.2: Satisfiability

Exercise 213. ▶ [M26] Experience with the analyses of sorting algorithms in Chapter 5 suggests that random satisfiability problems might be modeled nicely if we assume that, in each of $m$ independent clauses, the literals $x_j$ and $\bar{x}_j$ occur with respective probabilities $p$ and $q$, independently for $1 \le j \le n$, where $p + q \le 1$. Why is this not an interesting model as $n \to \infty$, when $p$ and $q$ are constant? Hint: What is the probability that $x_1 \cdots x_n = b_1 \cdots b_n$ satisfies all of the clauses, when $b_1 \ldots b_n$ is a given binary vector?

Verified: yes
Solve time: 1m47s

Setup

Let a random instance consist of $m$ independent clauses on the variables $x_1,\ldots,x_n$. For each clause and each variable $x_j$, the literal $x_j$ is included independently with probability $p$, and the literal $\bar{x}_j$ is included independently with probability $q$, where $p+q\leq 1$.

We must show that this model does not give an interesting asymptotic random satisfiability problem when $p$ and $q$ are fixed constants as $n\to\infty$.

Fix a binary assignment

$$ x_1x_2\cdots x_n=b_1b_2\cdots b_n, $$

where $b_j\in{0,1}$. Let $s$ be the number of variables assigned the value $1$:

$$ s=\sum_{j=1}^n b_j . $$

A clause fails to be satisfied exactly when it contains no literal that is true under this assignment.

Solution

For a variable with $b_j=1$, the literal $x_j$ is true and the clause is unsatisfied only if $x_j$ does not occur. The probability of this event is

$$ 1-p . $$

For a variable with $b_j=0$, the literal $\bar{x}_j$ is true and the clause is unsatisfied only if $\bar{x}_j$ does not occur. The probability of this event is

$$ 1-q . $$

The choices for distinct variables are independent, so the probability that one clause is not satisfied by the fixed assignment $b_1\cdots b_n$ is

$$ (1-p)^s(1-q)^{n-s}. $$

Therefore the probability that one clause is satisfied is

$$ 1-(1-p)^s(1-q)^{n-s}. $$

The $m$ clauses are independent, hence the probability that the fixed assignment satisfies every clause is

$$ \left(1-(1-p)^s(1-q)^{n-s}\right)^m . $$

This is the probability requested in the hint.

Now suppose that $p$ and $q$ are fixed constants. Choose the assignment that makes the more likely literal true. If $p\geq q$, take

$$ b_1=b_2=\cdots=b_n=1 . $$

For this assignment, $s=n$, and the probability that a single clause is violated is

$$ (1-p)^n . $$

If $q>p$, take

$$ b_1=b_2=\cdots=b_n=0 . $$

For this assignment, $s=0$, and the probability that a single clause is violated is

$$ (1-q)^n . $$

In either case, if

$$ a=\max(p,q), $$

the probability that the chosen fixed assignment violates one clause is

$$ (1-a)^n . $$

When $a>0$, we have

$$ 0<1-a<1, $$

$$ (1-a)^n\longrightarrow 0 $$

exponentially as $n\to\infty$.

Consequently, for any fixed number $m$ of clauses,

$$ \left(1-(1-a)^n\right)^m\longrightarrow 1 . $$

More generally, the same conclusion holds whenever $m$ grows more slowly than $(1-a)^{-n}$, because the probability that the fixed assignment fails at least one clause is bounded by

$$ m(1-a)^n , $$

which tends to $0$ in that range.

Thus a predetermined assignment satisfies almost every large random instance in this model. The clauses become so long that each clause is almost certain to contain a literal agreeing with any chosen assignment. Hence the model does not exhibit the interesting transition between satisfiable and unsatisfiable instances that appears in random $k$SAT models with bounded clause length.

The exceptional case $p=q=0$ is degenerate: every clause is empty and no assignment satisfies the instance. Apart from this case, the model is asymptotically trivial.

Verification

For a fixed assignment with $s$ ones, the unsatisfied-clause probability contains one factor for each variable. Each of the $s$ variables assigned $1$ contributes the absence probability $1-p$, and each of the $n-s$ variables assigned $0$ contributes the absence probability $1-q$. Therefore the exponent and the factors in

$$ (1-p)^s(1-q)^{n-s} $$

are determined independently and correctly.

The selected assignment maximizes the probability of satisfying a clause because it minimizes the probability that the only true literals are absent. Choosing all variables to favor the larger of $p$ and $q$ gives the smallest possible one-clause failure probability among constant assignments, namely

$$ (1-\max(p,q))^n . $$

Since this quantity decreases exponentially for fixed $\max(p,q)>0$, the claimed lack of an interesting asymptotic model follows.

Notes

The usual random $k$SAT model avoids this collapse by keeping the clause length bounded while letting the number of clauses grow proportionally to $n$. In the present model, the expected clause length is proportional to $n$, so each clause is almost always satisfied by any fixed assignment.