TAOCP 7.2.2.2 Exercise 195

Let $m=\lfloor(2^k\ln 2)n\rfloor$ be the number of random $k$SAT clauses.

taocpmathematicsalgorithmsvolume-4hm-medium

Section 7.2.2.2: Satisfiability

Exercise 195. [HM21] [HM21] (J. Franco and M. Paull, 1983.) Use the first moment principle MPR-(21) to prove that $\lfloor (2^k \ln 2)n \rfloor$ random $k$SAT clauses are almost always unsatisfiable. Hint: Let $X = \sum_v \lfloor x$-all clauses$\rfloor$, summed over all $2^n$ binary vectors $x = x_1 \ldots x_n$.

Verified: yes
Solve time: 1m33s

Solution

Let

$m=\lfloor(2^k\ln 2)n\rfloor$

be the number of random $k$SAT clauses. For a binary vector $x=x_1\ldots x_n$, define

$X=\sum_x I_x,$

where the sum is over all $2^n$ binary vectors and $I_x=1$ if and only if $x$ satisfies all chosen clauses. Thus $X$ is the number of satisfying assignments of the random formula.

For a fixed assignment $x$, a uniformly chosen random $k$SAT clause is unsatisfied exactly when all $k$ literals disagree with $x$. Each literal disagrees with probability $1/2$, independently, so

$\Pr(\text{$x$ does not satisfy a given clause})=2^{-k}.$

Hence

$\Pr(\text{$x$ satisfies a given clause})=1-2^{-k}.$

The clauses are chosen independently, therefore

$\Pr(I_x=1)=(1-2^{-k})^m.$

By linearity of expectation,

$E(X)=\sum_x E(I_x)=2^n(1-2^{-k})^m.$

Using $m=\lfloor(2^k\ln2)n\rfloor$, we have

$m\ge (2^k\ln2)n-1.$

Therefore

$E(X)\le 2^n(1-2^{-k})^{(2^k\ln2)n-1}.$

Separate the constant factor:

$E(X)\le \frac{2^n}{1-2^{-k}}\left((1-2^{-k})^{2^k}\right)^{n\ln2}.$

For $0<y<1$, the inequality

$\ln(1-y)<-y$

gives, with $y=2^{-k}$,

$\ln(1-2^{-k})<-2^{-k}.$

Multiplying by $2^k$,

$2^k\ln(1-2^{-k})<-1.$

Hence

$\left(1-2^{-k}\right)^{2^k}<e^{-1}.$

Raising both sides to the power $n\ln2$,

$\left((1-2^{-k})^{2^k}\right)^{n\ln2}<e^{-n\ln2}=2^{-n}.$

Substitution into the expectation bound yields

$E(X)<\frac{2^n}{1-2^{-k}}2^{-n},$

and consequently

$E(X)<\frac{1}{1-2^{-k}}.$

This estimate alone gives a constant bound, but the floor in $m$ leaves a constant loss. To obtain the required asymptotic statement, use the sharper expression before removing the floor:

$E(X)=2^n(1-2^{-k})^{\lfloor(2^k\ln2)n\rfloor}.$

Write

$\lfloor(2^k\ln2)n\rfloor=(2^k\ln2)n-r_n,$

where

$0\le r_n<1.$

Then

$E(X)=2^n(1-2^{-k})^{(2^k\ln2)n}(1-2^{-k})^{-r_n}.$

The final factor is bounded above by $(1-2^{-k})^{-1}$, while the first factor satisfies

= \left(2(1-2^{-k})^{2^k\ln2}\right)^n.$$ Taking logarithms of the base, $$\ln\left(2(1-2^{-k})^{2^k\ln2}\right) = \ln2+2^k\ln2\ln(1-2^{-k}).$$ Again using $\ln(1-y)<-y$, $$\ln2+2^k\ln2\ln(1-2^{-k}) < \ln2+2^k\ln2(-2^{-k}),$$ so $$\ln\left(2(1-2^{-k})^{2^k\ln2}\right)<0.$$ Therefore $$2(1-2^{-k})^{2^k\ln2}<1,$$ and hence $$E(X)\to0.$$ By the first moment principle MPR-(21), $$\Pr(X\ge1)\le E(X).$$ Since $E(X)\to0$, $$\Pr(X\ge1)\to0.$$ The event $X\ge1$ is precisely the event that the random $k$SAT formula has a satisfying assignment. Therefore the probability that the formula is satisfiable tends to zero, and the probability that it is unsatisfiable tends to one. Thus $\lfloor(2^k\ln2)n\rfloor$ random $k$SAT clauses are almost always unsatisfiable. $$\boxed{\Pr(\text{unsatisfiable})\to1}$$ This completes the proof. ∎