P与NP问题的研究进展

姜咏江

   自从SAT问题的子句消去法成功之后，我又转向了哈密顿回路的求解研究。我发现图的路径问题，同样可以转化为SAT问题来研究。所谓的哈密顿回路只不过是其SAT表达方式的一组有序全1特解而已。

1.             用数码0和1表示图

   在图的路径问题研究中，我发现将图的相邻顶点用数码0和1来表示，既简单，又明确。用1表示当前顶点，所有与之相邻的顶点用0表示。将每个顶点的这种表示做为一个子句，写到SAT表中（见表1和表2），这就是图的01表示法。

   例如，将图1（1）和图1（2）用0和1表达，则得到表1和表2的SAT表达式，最上面留出的一行用来标识顶点选取顺序。这种顶点选取顺序清楚地表达出了顶点到顶点间的路径。

   从表1和表2都可以看到，01表示的图所成SAT总有全为1的解。因而不难解释哈密顿回路问题是SAT问题解的条件特例。也就是说哈密顿回路的解一定是满足一定关联顺序条件的SAT全1解。

表1  图1（1）的SAT表示                          表2  图1（2）的SAT表示

2.             求图路径的子句消去法

    在图的01表示SAT路径问题中，选择某一个顶点，就是将变量的值定为1。因为每个选择的顶点都要设定值为1，选定变量的设定值就可以不写。我们不妨就用变量取值的位置来标注顶点选取的顺序。写上了顺序数，就代表选取了该顶点，没有顺序数的变量，就代表没有被选取。

为了清晰体现子句消去法来求解图的路径，依据子句消去法，我们规定：路径上后面一个顶点确定之后，就将前面顶点的子句消去。

   以表1为例。我们选3号顶点为路径起始点。

（1）找到x3值为1的子句（行），通过0值找到与这个顶点相邻的有2、4号顶点。

（2）选择2、4号顶点的一个，并消去x3=1的子句（在此以底纹表示）。这里选的是4号顶点。

（3）依据前面选定的子句，通过子句的0和1关联关系，如（2）去选择关联的顶点，直至不能够再选择为止或到达认定的终点。

   不难想象，如果全部顶点都能够被这种依据相邻的关系选中，并且可以确定最后选中的顶点与起始点相邻，那么该图就是一个哈密顿图，所选的闭合路径就是哈密顿回路。在得到哈密顿回路的时侯，SAT的全部子句都会被消去（参考表1和图1（1））。不然，没有哈密顿回路，SAT的子句也不会全部消去（参考表2和图1（2））。

3.             路径边消去法

   在图的路径问题研究中，我们可以从某点开始，除去起始点和终点之外，只将前面选择的顶点和关联边留下，其余的边都消去，这样就可以得到需要的路径（见图2和图3）。如果我们要求解的是一条回路，那么起始点也是终点，最后要消去起始点所有未选中的边（见图4）。

   很明显，图路径的边消去法，就是图01表示的子句消去法。

4.             求哈密顿回路

   依据子句消去法，并依据一定的规则就可以求出哈密顿回路。自然，当一个图不是哈密顿图时，也就求不出哈密顿回路。在客观上，这种方法找到了鉴别一个图是否是哈密顿图的方法。

   SAT的子句消去法是一种多项式时间复杂度的算法。图的边消去法求解哈密顿回路，也是一种多项式时间复杂度的算法。

   目前，本人对任意给出的图都能够求出是否有哈密顿回路，即可鉴别是否是哈密顿图。只是在理论证明上尚未完成。如有人愿意与本人一同合作研究，可以与我直接联系。

邮箱：accsys@126.com

2016-02-24