深入研究子句消去法 姜咏江 多项式 C n k +C n k-1 +...+C n 1 +C n 0 与 2 n 相差多少？其实，只要 k=n ，那么前者就是后者。只有当 k 为常数的时侯，多项式与指数时间复杂度才有明显的时间效益。 k 为常整数，求由比 k 少的逻辑变量取值形成子句间与运算表达式结果为真值，就是 SAT 问题。如今 SAT 问题 ...
姜咏江 SAT 的定义中是不允许出现重复子句的，但在子句消去的过程中，会出现降阶的子句块中有重复的子句。 t 阶子句块变量唯一解是因为它有 2 t-1 个相同的表现值（ 1 ≤ t ≤ k ）。在消去子句的过程中很难事前知道那些子句会重复，这样证明消去重复子句这一步算法时间复杂度为多项式时间就很困难。不过我们 ...
姜咏江 用 n 个逻辑变量和其变量非形式中的不超过 k （ k 是一个常数）个，写出若干个或运算多项式（子句），问能不能设定这 n 个变量的一组值（是一个 n 位二进制数），使每一个多项式的逻辑值都是 1 （真）？这个问题就是被国外认定的世界难题 SAT 。 举个例子，有逻辑变量 x 1 , x 2 , … , x 5 ...
博文
视频
基金
相册
收藏
积分
会议