A New Approach on Solving 3-Satisfiability
A New Approach on Solving 3-Satisfiability
复制标题
求解 3-可满足性的新方法
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
R. Rodosek
中科院分区：
文献类型：
--
作者：
R. Rodosek
在本文中，我们描述和分析的算法解决3-可满足性问题。如果把子句看作约束满足问题的约束条件，那么每个子句都表示一个具有特殊性质的约束条件，即子四边形。我们证明了该算法在子四边形保证解决方案的时间小于O（1.476n），这改善了目前著名的3-可满足性算法。测试表明，与其他算法相比，平均步数也明显较小。
In this paper we describe and analyse an algorithm for solving the 3-satisfiability problem. If clauses are regarded as constraints of Constraint Satisfaction Problems, then every clause presents a constraint with a special property, namely subquadrangle. We show that the algorithm on subquadrangles guarantees a solution in time less than O(1.476n), which improves the current well-known 3-satisfiability algorithms. Tests have shown the number of steps to be significantly smaller also in the average compared with the other algorithms.