A Combinatorial Analysis for the Critical Clause Tree

作者：Yamamoto Masaki^*

来源：Theory of Computing Systems, 2013, 52(2): 271-284.

DOI：10.1007/s00224-012-9383-6

• Critical clause tree
• k-SAT

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-mu k/(k-1)+epsilon k(d))n), where mu(k)/(k - 1) = Sigma(infinity)(i=1) 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) = Sigma(d)(i=1) 1/(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 = omega(1).

• 出版日期2013-2