__
TR10-095 | 11th June 2010 03:09
__

#### A combinatorial analysis for the critical clause tree

**Abstract:**
In [FOCS1998],

Paturi, Pudl\'ak, Saks, and Zane proposed a simple randomized algorithm

for finding a satisfying assignment of a $k$-CNF formula.

The main lemma of the paper is as follows:

Given a satisfiable $k$-CNF formula that

has a $d$-isolated satisfying assignment $z$,

the randomized algorithm finds $z$

with probability at least $2^{-(1-\mu_k/(k-1)+\epsilon_k(d))n}$,

where $\mu_k/(k-1)=\sum_{i=1}^{\infty}1/(i((k-1)i+1))$,

and $\epsilon_k(d)=o_d(1)$.

They estimated the lower bound of the probability in an analytical way,

and used some asymptotics.

In this paper,

we analyze the same randomized algorithm,

and estimate the probability in a combinatorial way.

The lower bound we obtain is a little simpler:

$2^{-(1-\mu_k(d)/(k-1))n}$,

where $\mu_k(d)/(k-1)=\sum_{i=1}^{d}1/(i((k-1)i+1))$.

This value is a little bit larger than that of [FOCS98]

although the two values are asymptotically same when $d=\omega(1)$.