3-SAT问题为什么长期得不到解决？

3-SAT是解决P/NP问题的关键问题之一，可就是长期得不到有效的解法，原因在哪里呢？

第一、人们过于将3-SAT问题做为整体性问题来求解了。

例如，随便写出100个变量的3-SAT，如果你将3个逻辑变量的子句放到一起，如果同变量的子句有8个（不包括同一变量正反都在的子句），那么3-SAT肯定就没有满足解。但是，如果将那些子句无规律地放到一起，这种易于判断的特征就消失了。

再如，没有共同逻辑变量的子句之间是无关的，因而各自变量值的变化不影响局部的求解。

第二、3-SAT的关联段解决定着整体的解。

3-SAT是否有解是由那些相互有共同变量关联的段来决定的。关联段分为一元关联，二元关联和三元关联。3-SAT的三元关联的段之间是相互独立的，不会超过8个子句（不包括同一变量正反都在的子句）。二元关联和一元关联会形成长段。实际上，关联段是3-SAT的基本组成部分，只要这些基本组成的关联段都有解，那么3-SAT整体才有解；只要其中任何一个关联段无解，3-SAT整体就无解。

第三、每个3-SAT的关联段最多需要7次求解过程就可以将该关联段的解都求出。

关联段解的长度是由段中包含的逻辑变量数来确定的。用分段子句消去法求解的次数是由起始子句块的可能解数量确定的。有解的子句块最多有7个可能解，因而关联段最多要进行7次求解过程。

第四、利用分段子句消去法才能够在求解中判断出变量应该的取值。

由于3-SAT关联段是否有解要看关联变量之间的相互制约情况。这其中制约最简单的情况是2个变量值已经确定，看所有通过第三个变量相关的子句是否能都设定这一个变量值消去。复杂些的是有一个变量值确定的有2个共同变量的子句，是否可以找到这两个变量的值，将这些子句全部消去。分段子句消去法给出了关联段求解中有一解和无解的判断方法，并且给出了有2个解的延续处理方法，从而能够顺利地求出关联段的解。

分段子句消去法给出的这些函数方法是以往3-SAT研究中未见有人使用过的。

2015-11-2