为什么子句分段消去法可以求出3SAT的解？

姜咏江

A proof that P = NP could havestunning practical consequences, if the proof leads to efficient methods forsolving some of the important problems in NP.

上面这句话引自维基百科的P versus NP。说得是否有些过分了？

用子句分段消去法求解3-CNF=1的解，首先是将逻辑变量表达的问题结构化了，这种3-CNF特有的结构是求解的基础。子句间形成的子句块制约了子句中逻辑变量的自由变化，使3-CNF=1的解转化成了局部的“子句块解”和“关联段解”，从而避开了处处要从全局变量变化来确定逻辑变量值的传统方法。

子句块中子句数量的变化，为我们揭示了变量取值的规律，而关联段求解中产生的动态块，又为我们指明了段中变量值变化的规律和相互制约关系。所以我们才能够依据这些3-CNF中变量变化的内在规律，找到求解3-SAT问题满足解的方法。这是一种函数关系的体现，

不客气地说，我是计算机科学理论方法的里手，仔细研究，这个P/NP问题应该是纯数学的问题，它与计算机程序运行的时间计算等关系并不十分紧密，将其说成是计算机运行时间的问题不够贴切，因为计算机程序运行时间只与指令重复执行次数相关。

2015-10-16