A Combinatorial Analysis for the Critical Clause Tree

摘要

In Paturi, Pudlak, Saks, and Zane (Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS1998), pp. 628-637, 1998) 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=1)~∞1/(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) =∑_(i=1)~d1/(i((k-1)i+1)). This value is a little bit larger (i.e., better) than that of Paturi et al. (Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS1998), pp. 628-637,1998) although the two values are asymptotically equal when d = ω(1).