PPSZタイプの充足可能性判定アルゴリズムの成功確率増幅について

概要

論文の詳細を見る
Recently, [Iwama, Tamaki, SODA04] gave a new worst-case upper bound for 3SAT by modifying the PPSZ-type algorithm in [Paturi et. al., FOCS98] by making use of the local-search-type one in [Schoning, Algorithmica 02]. We propose a different kind of modification in this paper. Recall that the analysis of the first algorithm (denoted by PPSZ) assumes that each bit of the initial assignment coincides that of a satisfying assignment with probability one half. Our idea is that if we can increase this probability, i.e., if we can use a "better" initial assignment, then the success probability of PPSZ should increase. To get this better assignment we use the second algorithm (denoted by SCH). Note that the local search starts with a random assignment and gradually approaches to a satisfying assignment z. In the middle of this process, there should be the moment that the current assignment a^* is close to z and to use PPSZ with this assignment a^* has a better success probability than to continue SCH. In this paper we prove that this conjecture is true under some assumption on the uniformity of probability.
社団法人電子情報通信学会の論文
2006-03-16