An Improved Upper Bound for SAT
An Improved Upper Bound for SAT
复制标题
改进的 SAT 上限
DOI：
10.1007/11499107_31
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Wolpert
中科院分区：
文献类型：
--
作者：
E. Dantsin;A. Wolpert
给出了一种不受子句长度限制的布尔合范式公式可满足性的随机化检验算法。它的运行时间最多为2n(1−1/α)，直到一个多项式因子，其中α = ln (m/n) + O(ln ln m), n， m分别为输入公式中变量的个数和子句的个数。这个边界渐近地优于之前已知的SAT的2n（1−1/log(2m)）边界。
We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most 2n(1−1/α) up to a polynomial factor, where α = ln (m/n) + O(ln ln m) and n, m are respectively the number of variables and the number of clauses in the input formula. This bound is asymptotically better than the previously best known 2n(1−1/log(2m)) bound for SAT.