学术研究常常需要你改变思路

姜咏江

学术研究和创新科研常常需要你改变前人的思路，如此才有希望获得独到的成就。我现在可以完全肯定3-SAT问题已经被我解决了。3-SAT就是一个初等数学的问题。一个初等数学就能够解决的问题，被学术界说得如此神乎其神，其原因多半是研究中缺乏及时地改变思路所至。

搞学术或科研，自然免不了先要学习前人或别人的许多东西，自然免不了要顺着人家的思路进行研究思考，这是学术研究的惯性。但是，如果沿着那种成型的思路走不下去的时侯，就应该考虑换个角度或方法研究，这样才会有所发现。

我在机器计算基础研究中发现了限位数理论和方法，因而才想到将k-CNF-SAT的子句按照k个变量组织到一起，看看有什么特征。这就是“子句块”和“关联段”。我这种变换角度的思考方法，是我获得3-SAT解法成功的关键。有了子句块和关联段的概念，再对之施行“子句消去法”，那么不仅3-SAT是个初等数学问题，就连k-CNF-SAT也都是初等数学问题！

我进入P/NP问题的研究过程就记录在科学网上。说起我进入P/NP问题的研究，那是一个完全偶然的事情。我擅长的是计算机CPU设计，2014年在网上介绍CPU设计的重要性之时，被李斌网友提及P/NP问题才是重大的科研问题所吸引。于是就以玩玩的态度，在科学网上做起了P/NP问题的学术研究。这其中最大的目的还是想活动活动大脑，顺便在网上结交一些朋友。

我起先以为P/NP问题关乎到程序运行时间计算问题。因而抛出了程序执行时间计算方法的博文，被李斌嘲笑我根本没有弄清楚P/NP问题。这期间免不了要深入学习什么是P/NP问题，最后落实到3-SAT的求解方法。

子句消去法是分段子句消去法的简称。“逻辑多项式的某项值为1，那么这个逻辑多项式的值就是1”，这就是子句消去法的基本原理。这一简单的原理恐怕没有什么人不清楚。如果一个个设定逻辑变量的值，子句消去法无疑是一种穷举的方法，不是多项式时间的算法。但我相信，找到合取范式k-CNF的结构规律，一定会找出规律的计算方法。说实话，这其中我有若干次想放弃，对一些批评和讥讽感到有理。一个半个多世纪都未被学术界解决的问题，你一个七十岁的老者能够破解？兴趣是学术研究最大的动力，这方面也许有人不信，但我确实是被兴趣所驱使，一种不想失败的想法激励着我继续。事实证明我成功了，我自己也就轻松了。

用子句消去法求解3-CNF=1的解，每一个中学生都可以学会，这不就是一个初等数学问题？既然是初等数学问题，为何长期得不到解决？

其实，k-SAT问题涉及到一种离散型关联关系的计算，而这种计算并不是通常的算术运算所能够解决的。算术运算是一种连续地因果关系的思维模式，其极致就是数学分析的微积分思想。离散型关联关系的因素之间只为相互结构所左右，而不具备因果关系的那些显著特征。离散关联关系形成问题的结果只需要回答是否，而不会像我们所通晓的数那样分为相互关联的级别。

例如，逻辑变量表达式(x’₁+ x’₂+ x’₃)(x₁+ x’₂+ x’₃)(x’₁+ x₂+ x’₃)(x₁+ x₂+ x’₃)(x’₁+ x’₂+ x₃)(x₁+ x’₂+ x₃)(x’₁+ x₂+ x₃)(x₁+ x₂+ x₃)，不论我们给出逻辑变量x₁、 x₂、 x₃怎样的值，该表达式最终的结果一定是0，这是逻辑变量间的结构造成的。这种多因素的结构关联，在以往的研究中缺失很多。显然书写成上面这种表达式的方式不利于结构因素研究。将上面的表达式写成下面表1的形式（x_i用1记录，x’_i用0记录），就能够一目了然地看出变量之间的相互制约关系。

由表1 可以看出，我们将每一行看作一个子句，无论我们对x₁、 x₂、 x₃设定怎样的值，都不能够将全部子句消去。而去掉表1中的某些行，那么就可以设定x₁、 x₂、 x₃的值将子句全部消去。

表1  3-CNF完全子句块

对于3-CNF来说，设定x₁、 x₂、 x₃的值后，能消去3-CNF的全部子句，就等于求出了3-CNF=1的解。所以逻辑变量间的结构如何就成了k-CNF=1求解的钥匙。

子句块之间的相互关联结构也影响到k-CNF=1求解，这是离散因素结构分析的必然。表上有限次操作无疑是一种多项式时间复杂度的算法。

一年多的时间，我能够完成3-CNF=1的求解方法，关键的地方是改变了以往人们的思考路线，引进了表结构方式，从而找到了k-CNF=1求解的基本途径。

按照维基百科网站上的说法，P/NP问题涉及的科研层面太广了，解决了3-SAT问题就等于解决了P/NP问题。一般认为，NPC的典型3-SAT的多项式时间求解存在，就等同于P=NP。这究竟是否完全正确，我还没有详细地研究。

2015-12-23