TAOCP 7.2.2.2 Exercise 194

Section 7.2.2.2: Satisfiability

Exercise 194. [HM19] [HM19] If $\alpha < \liminf_{n\to\infty} S_{k,n}/n$, is there a polynomial-time algorithm that is able to satisfy a random $m$SAT clauses with probability $\ge \delta$, for some $\delta > 0$?

Verified: yes
Solve time: 1m30s

Solution

Let $m=\alpha n$. The hypothesis is

$$ \alpha<\liminf_{n\to\infty}\frac{S_{k,n}}{n}. $$

By the definition of the satisfiability threshold in equation (81), this inequality places the density $\alpha$ strictly below every subsequential limiting lower bound of the random $k$SAT threshold. Therefore, for all sufficiently large $n$, a random instance with $m=\alpha n$ clauses is satisfiable with probability tending to $1$.

The question asks for substantially more than satisfiability. A satisfying assignment must be produced by an algorithm whose running time is polynomial in $n$, and the algorithm must succeed with probability at least some fixed constant $\delta>0$. The threshold only gives information about the existence of satisfying assignments. It does not provide a method for finding them.

A trivial search through all assignments takes $2^n$ trials. For a uniformly random assignment, the probability of satisfying a random $k$SAT clause is

$$ 1-2^{-k}, $$

so the expected fraction of assignments satisfying a random formula with $m=\alpha n$ clauses is

$$ (1-2^{-k})^{\alpha n}, $$

which is exponentially small in $n$ for fixed positive $\alpha$. Thus random sampling does not give a polynomial-time algorithm with constant success probability.

Known algorithms solve random $k$SAT efficiently only up to certain densities below the satisfiability threshold. The existence of an efficient algorithm all the way up to every density satisfying

$$ \alpha<\liminf_{n\to\infty}\frac{S_{k,n}}{n} $$

is not known in general. The satisfiability threshold and the algorithmic threshold need not coincide, and proving that they do coincide would require new results about the structure of random satisfiable formulas and efficient search procedures.

Hence the requested algorithm is not currently known to exist. The question remains open.

$$ \boxed{\text{No such polynomial-time algorithm is known in general; the problem is open.}} $$