你有SAT问题？我来帮你解答

姜咏江

我们不谈3-SAT问题是否是关系到开放的P/NP问题，只谈3-SAT问题的求满足解的算法快慢。如果你的问题可以转化为布尔电路可满足性问题，那么很幸运，这个问题有了在一定变量数之后，较指数时间快的多项式时间算法了。

本人宣布过在理论上解决了SAT问题的多项式时间算法。如今我已经将理论转化成了计算机软件程序CESAT。最坏的3-SAT问题，CESAT程序可以在O(n⁴)时间复杂度内得到满足解。根据研究，在变量数充分大之后，指数时间复杂度的求解程序无法在短时间内获得结果，而多项式时间复杂度的程序CESAT可以做到。

下面是CESAT程序运行时间测试。

例子1.  有200个变量和500个子句的3-SAT，程序运行时间和结果如图1所示。

图1  CESAT的执行结果与运行时间

图1中开始的时间是11：10：35，找出全部唯一解变量的时间是11：15：42，中间程序运行5分7秒。另外，程序结束的时间是11：15：45，总共运行的时间是5分10秒。

这是一般情况下的求3-SAT满足解的例子。为了说明CESAT的快速，再执行一个对子句消去法最坏情况的例子。

例子2.  图2为所有变量都有2个可选解的3-CNF。这是将其前11列连续编排10次，得到了有110个变量的3-CNF。CESAT在求解的过程中要判断每个变量的可选解数量，由于没有唯一解变量，因而会消耗较多的时间。

图2   变量全为2个可选解

CASAT对此题进行的测试，用了33分钟17秒。如图3所示，唯一解部分没有任何变量值，全部变量值都出现在有2个可选解的情况。

图3  CASAT得出结果运行时间

上面两个例子反映出了CESAT程序针对3-CNF=1求解的实际情况。毫无疑问，在变量充分一样多，最坏的情况下也会体现出CESAT的快速本质。

为了清楚，我们简单说明一下指数时间和多项式时间的问题，以及CESAT的优势。

最简单的指数函数为y=2ⁿ，而4次多项式为y=a₀+a₁n¹ +a₂ n² +a₃ n³ +a₄ n⁴。依据算法时间复杂度理论，计算机操作时间计算，只要比较多项式的最高项即可。在计算机中可以取2的幂的数，于是选有n=2^m。这样就有2的2^m次幂与2^4m相等的点，即有2^m=4m这个时间点。容易得到m超过4，也就是n超过16就可以满足指数时间超过4次多项式时间的要求。全面考虑多项式，总可以找到一个确定的n₀，使n继续变大的时候，y=2ⁿ的上升速度高于y=a₀+a₁n¹ +a₂ n² +a₃ n³ +a₄ n⁴。

一般情况下，不要以为算法的多项式时间就是一、二次多项式那样快。3-SAT问题一般情况，最低要超过有65536个变量的情况下，才可以说多项式y=a₀+a₁n¹ +a₂ n² +a₃ n³ +a₄ n⁴算法比y=2ⁿ这个指数时间算法要快。但子句消去法CESAT的优势是依据限位数理论，快速找出了那些有唯一解的变量值，进而可以大大地减少了需要重复操作的变量的数量，并依据剩余变量可选解集做为记忆的形式，通过“联想”和“忘记”迅速获得满足解。这种特征无疑是人工智能的理论和实现基础。

我没有编写和使用过DPLL程序。用过DPLL程序的朋友，一定会有客观的感受。

相信我，就可以联系我。

2017-06-02