Solving 3-Satisfiability in Less Then 1, 579n Steps
Solving 3-Satisfiability in Less Then 1, 579n Steps
复制标题
用少于 1, 579n 个步骤求解 3-可满足性
DOI：
10.1007/3-540-56992-8_22
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
I. Schiermeyer
中科院分区：
文献类型：
--
作者：
I. Schiermeyer
在本文中，我们描述并分析了一种用于解决3 - 可满足性问题的改进算法。如果F是一个具有n个变量和r个子句的合取范式的布尔公式，那么我们将表明该算法能够在小于O(1.579^n)的时间内解决每个子句至多有三个文字的公式的可满足性问题。
In this paper we describe and analyse an improved algorithm for solving the 3-Satisfiability problem. If F is a boolean formula in conjunctive normal form with n variables and r clauses, then we will show that this algorithm solves the Satisfiability problem for formulas with at most three literals per clause in time less than O(1,579n).