期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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−k(k−1)+k(d))n ,
where k(k−1)=i=11(i((k−1)i+1)) ,
and k(d)=od(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−k(d)(k−1))n ,
where k(d)(k−1)=di=11(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=(1).
