A Probabilistic 3-SAT Algorithm Further Improved
A Probabilistic 3-SAT Algorithm Further Improved
复制标题
进一步改进的概率3-SAT算法
DOI：
10.1007/3-540-45841-7_15
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
O. Watanabe
中科院分区：
文献类型：
--
作者：
T. Hofmeister;U. Schöning;R. Schuler;O. Watanabe
Schöning在[Sch 99]中提出了一个简单而有效的随机算法来求解k-SAT问题。在3-SAT的情况下，当给定公式Fonnvariables时，该算法的预期运行时间为poly（n）·E（4/3）n=O（1.3334n）。这是迄今为止已知的求解3-SAT的算法的最佳运行时间。在这里，我们描述了一种算法，通过将上述随机化算法的改进版本与其他随机化算法相结合来改进该时间约束。我们新的3-SAT的预期时间界为O（1.3302n）。
In [Sch99], Schöning proposed a simple yet efficient randomized algorithm for solving thek-SAT problem. In the case of 3-SAT, the algorithm has an expected running time of poly(n)·E(4/3)n=O(1.3334n) when given a formulaFonnvariables. This was the up to now best running time known for an algorithm solving 3-SAT. Here, we describe an algorithm which improves upon this time bound by combining an improved version of the above randomized algorithm with other randomized algorithms. Our new expected time bound for 3-SAT isO(1.3302n).