Improved Exponential Algorithms for SAT and ClSP
Improved Exponential Algorithms for SAT and ClSP
复制标题
改进的 SAT 和 ClSP 指数算法
DOI：
10.3929/ethz-a-010512781
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Timon Hertli
中科院分区：
文献类型：
--
作者：
Timon Hertli
布尔公式的可满足性（SAT）是最突出的np完全问题之一。我们考虑k- sat，一个决策问题，它询问大小最多为k的子句的合取范式（CNF）公式是否可满足，以及一个更一般的问题，称为（d, k）ClSP（子句满足问题），其中变量是d值而不是布尔值。对于k- sat和(d, k)-ClSP，已经提出了许多算法，其运行时间在输入公式的变量数量上是“适度指数”的。其中最快的k-SAT随机化算法是由Paturi， Pudlak, Saks, and Zane （FOCS 1998）提出的PPSZ算法。我们重新分析了PPSZ算法，并表明在输入公式最多有一个令人满意的赋值（唯一k- sat）的情况下所显示的界一般成立，而以前只知道k≥5。我们还展示了如何将PPSZ推广到(d, k)-ClSP，改进了之前大多数考虑（d, k）值的算法。此外，我们还提出了一种新的基于PPSZ的3-SAT算法，该算法具有指数更好的界。对于一般k，我们证明了为了提高k- sat的PPSZ，提高唯一k- sat的PPSZ就足够了。
Satisfiability of Boolean formulas (SAT) is one of the most prominent NP-complete problems. We consider k-SAT, the decision problem that asks whether formulas in conjunctive normal form (CNF) with clauses of size at most k are satisfiable, and the more general problem called (d, k)ClSP (clause satisfaction problem) where the variables are d-valued instead of Boolean. For k-SAT and (d, k)-ClSP many algorithms have been presented whose running time is “moderately exponential” in the number of variables of the input formula. One of the fastest randomized algorithm for k-SAT is the PPSZ algorithm by Paturi, Pudlak, Saks, and Zane (FOCS 1998). We re-analyze the PPSZ algorithm and show that the bounds shown in the case where the input formula has at most one satisfying assignment (Unique k-SAT) hold in general, which was previously only known for k ≥ 5. We also show how to generalize PPSZ to (d, k)-ClSP, improving on the previous algorithms for most considered values of (d, k). Furthermore, we present a new algorithm based on PPSZ with exponentially better bounds for 3-SAT. For general k we show that in order to improve on PPSZ for k-SAT, it is enough to improve on PPSZ for Unique k-SAT.
改进的 3-SAT 随机算法
DOI：
--
发表时间：
2010
期刊：
Proceedings of the 21^<st> International Symposium on Algorithms and Computation, LNCS
影响因子：
--
作者：
K.Iwama;K.Seto;T.Takai;S.Tamaki
通讯作者：
S.Tamaki
在 STDk/3[k ;
DOI：
--
发表时间：
2008
期刊：
Discrete Mathematics 308
影响因子：
--
作者：
Y. Hiramine;C. Suetake;K. Akiyama C. Suetake
通讯作者：
K. Akiyama C. Suetake