Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-095 | 11th June 2010 03:09

A combinatorial analysis for the critical clause tree


Authors: Masaki Yamamoto
Publication: 12th June 2010 09:06
Downloads: 3130


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:
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