论文标题
SAT的改进上限
An Improved Upper Bound for SAT
论文作者
论文摘要
我们表明，可以解决CNF满意度问题$ O^*（1.2226^m）$时间，其中$ m $是公式中的条款数量，改善了Yamamoto 15年前给出的已知上限$ o^*（1.234^m）$，而$ o^*（1.239^m）$由hirs $ 22年了。通过使用摊销技术和仔细的病例分析，我们成功地避免了以前的算法中的瓶颈并进行改进。
We show that the CNF satisfiability problem can be solved $O^*(1.2226^m)$ time, where $m$ is the number of clauses in the formula, improving the known upper bounds $O^*(1.234^m)$ given by Yamamoto 15 years ago and $O^*(1.239^m)$ given by Hirsch 22 years ago. By using an amortized technique and careful case analysis, we successfully avoid the bottlenecks in previous algorithms and get the improvement.
