姜咏江

学术研究并不都需要秘密地进行，特别是那些所谓的世界难题一类，公开在科学网上研究论证，不怕讥笑和嘲讽，借助于批评者，能够获得快意和驱动力，激奋你快速前进。这是我两年多钻研子句消去法求解SAT问题满足解的特有体会。

两年中，我从无知SAT问题到有所收获，除了我自身的数学和计算机的功底之外，探索科学的强烈兴趣是我研究重要的动力。我将所有的不同见解作为参考，也作为鼓励自己前进动力的一部分，提醒自己，要善待或感谢那些嘲讽与讥笑，最后收获的将一定是由衷的快乐。

证明子句消去法是多项式时间算法确实很艰难。虽然我构造了子句块、关联段、变量可选解、降阶子句块等概念，并运用限位数理论解决了变量无解和唯一解形式的判断，以至于证明了每个变量都有2个可选解的SAT，都可以用子句消去法求出满足解，但证明子句消去法是多项式时间复杂度的算法仍然是艰难的。这种艰难源自于消去子句过程中，要删除子句块中的重复子句，或者要涉及到数排序。

大家知道，k-SAT中n个变量的k个变量子句最多有2^kC_n^k个，去重复的过程中，子句数不会超过这个数，要用通常的去掉重复子句的方法，最坏大概要进行2^kC_n^k的阶乘次比较。显然，这不是一个多项式时间可以完成的问题。解决这个问题需要懂得计算机硬件设计方面的知识。设计一个带有存储单元空满标志的存储器，并实行数据标记单元存储法，这个问题就转化成多项式时间算法了！核心思想就是将二进制表示的子句，放到这个数为地址的存储单元（专家排序法 http://blog.sciencenet.cn/blog-340399-995138.html  ）去掉重复，然后通过标志来选择操作这些数据。

SAT问题不仅是一个数学和计算机软件程序设计的问题，它是一个用数学理论、计算机设计制作理论与方法的综合性问题。

限位数理论是我早年的研究，SAT问题的解决中逼出来了专家排序法。不管今后这些方法会起到怎样的作用，作为一个凭借兴趣探讨学问的人都会有幸福感。公开搞学术的好处是可以借助别人的批评快速进步，最大的体会就是要经得起冷嘲热讽。

2016-11-5