Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-095 | 11th June 2010 03:09

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

TR10-095
Authors: Masaki Yamamoto
Publication: 12th June 2010 09:06
Keywords:

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)$.

ISSN 1433-8092 | Imprint