TAOCP 7.2.2.2 Exercise 164

Exercise 164. [M30] [M30] Continuing exercise 163, bound the running time when $F$ is kSAT.

Verified: no
Solve time: 2m06s

Solution

Let $T_k(n)$ be the maximum number of executions of steps R1, R2, and R3 made by the procedure $R(F)$ of exercise 163 when $F$ is a $k$SAT formula with $n$ variables. We assume $k\geq 2$.

The argument of exercise 163 depends only on the fact that the clause selected in step R1 has bounded size. For a $k$SAT formula, every clause has size at most $k$, so the same branching argument applies with a $k$-dependent recurrence.

Suppose the clause chosen in step R1 is

$$ C={l_1,l_2,\ldots,l_s}, $$

where $s\leq k$. If $s=1$, or if the clause leads to an immediate reduction by step R2, the number of remaining variables decreases without creating the full branching pattern. Hence the worst case occurs when no such simplification is available.

The procedure tries the literals of $C$ in reverse order. The first recursive call assigns $l_s$ to be true, giving a subproblem with at most $n-1$ remaining variables.

If this branch fails, then $l_s$ must be false in every satisfying assignment extending the current branch. The next attempt assigns $l_{s-1}$ to be true while retaining $l_s=0$. Thus the second recursive call fixes two variables and has at most $n-2$ variables remaining.

Continuing in this way, the possible recursive calls correspond to the first literal in the sequence

$$ l_s,l_{s-1},\ldots,l_1 $$

that is assigned the value $1$. The $i$-th such possibility fixes $i$ variables, so the recursive subproblems have sizes

$$ n-1,n-2,\ldots,n-s. $$

If all $s$ literals are assigned false, the clause becomes empty and the branch terminates without another recursive call. Therefore, for some constant $c_k$,

$$ T_k(n)\leq T_k(n-1)+T_k(n-2)+\cdots+T_k(n-s)+c_k . $$

Because all terms on the right are nonnegative, the largest possible upper bound occurs when $s=k$. Indeed, for every $s<k$,

$$ T_k(n-1)+\cdots+T_k(n-s) \leq T_k(n-1)+\cdots+T_k(n-k), $$

where the additional terms are nonnegative. Hence

$$ T_k(n)\leq T_k(n-1)+T_k(n-2)+\cdots+T_k(n-k)+c_k . $$

It remains to solve this recurrence.

Define $S_k(n)$ by

$$ S_k(n)=S_k(n-1)+S_k(n-2)+\cdots+S_k(n-k), $$

with sufficiently large initial values so that $T_k(n)\leq S_k(n)$ for all $n$ below the initial threshold. The additive constant in the recurrence for $T_k$ can be absorbed into this comparison by increasing the initial values by a fixed amount, so it suffices to bound $S_k(n)$.

The characteristic equation of this homogeneous recurrence is

$$ x^k=x^{k-1}+x^{k-2}+\cdots+x+1 . $$

Let $\alpha_k$ be its real root greater than $1$. To see that this root exists and is unique, divide the equation by $x^k$. For $x>1$ it becomes

$$ 1=\frac1x+\frac1{x^2}+\cdots+\frac1{x^k}. $$

Equivalently, define

$$ f(x)=1-\frac1x-\frac1{x^2}-\cdots-\frac1{x^k}. $$

Then

$$ f(1)=1-k<0, $$

while

$$ \lim_{x\to\infty}f(x)=1>0. $$

Furthermore,

$$ f'(x)=\frac1{x^2}+\frac2{x^3}+\cdots+\frac{k}{x^{k+1}}>0 $$

for every $x>1$. Hence $f$ is strictly increasing on $(1,\infty)$, so it has exactly one zero there. This zero is $\alpha_k$.

Standard linear recurrence theory now gives

$$ S_k(n)=O(\alpha_k^n), $$

and therefore

$$ T_k(n)=O(\alpha_k^n) $$

provided the total cost of all recursion nodes is also bounded.

The recurrence above already bounds the number of recursive calls. To include the work done at every node, let $N_k(n)$ denote the total number of executions of R1, R2, and R3. Each recursive node contributes at most a constant amount of local work, and its children correspond to the same subproblems as before. Therefore

$$ N_k(n)\leq N_k(n-1)+N_k(n-2)+\cdots+N_k(n-k)+d_k $$

for a constant $d_k$. This is the same recurrence shape as the one for $T_k(n)$, so the same comparison argument gives

$$ N_k(n)=O(\alpha_k^n). $$

Thus the complete running time, including the work performed at internal nodes as well as leaves, has the required bound.

For $k=3$, the defining equation is

$$ \alpha_3^3=\alpha_3^2+\alpha_3+1, $$

whose root greater than $1$ is

$$ \alpha_3=1.839286\ldots . $$

This is the same exponential factor obtained in exercise 163.

Therefore, for $k\geq2$, the running time of $R(F)$ on $k$SAT formulas with $n$ variables is

$$ \boxed{ O(\alpha_k^n), \qquad \alpha_k^k=\alpha_k^{k-1}+\alpha_k^{k-2}+\cdots+\alpha_k+1 } $$

where $\alpha_k$ is the unique real root greater than $1$ of the displayed equation.

$\square$