姜咏江

有一段时间没写博文了，原因很简单，忙着将子句消去法写成计算机程序。说实在的，对一个七十多岁的人来说，还真是有点玩命。但我这个人办事不愿意半途而废。今天是“五一”劳动节，我确实还真地劳动了一番，将求3-SAT满足解的程序彻底完成了。高兴之余，想起来写点，以作为纪念。

为什么要拼命自己编程？很简单，别人编不来。我说我解决了SAT问题的多项式时间算法，大概没有什么人会相信，因为中涉及到了P/NP这个几十年未能够解决的计算机科学的世界难题，世界上那么多聪明的科学家，数学界、计算机界的名人名家都未能解决，你就解决了？其实，这是一般人的习惯看法。但事情总有特殊性，我就是那种特殊的人物。

SAT问题的全解和满足解问题，我都在理论上解决了。可是要学界的人们认可你，那可不是一件容易的事情。特别是在我们中国，就更是困难。原因是一般学者说了不算，而权威名家一般都不会轻易说出自己的见解，P/NP问题毕竟是全世界都一直未能解决的头号难题。为了让学术界认可，需要做艰苦细致地工作，其中最重要的是拿出“真东西”来！真东西是什么？就是实际能够求SAT满足解的程序。说起来，这就是我非要玩命设计出求解SAT 解问题程序的根本原因。

我说过，子句消去法求3-SAT的满足解时间复杂度不超过O(n⁴)，通过我写出的程序执行，完全可以证实这个结论。上百个变量的3-SAT求解，在我的笔记本上十几秒就可以得到结果。顺便说一句，那种用随机的方法产生的合取范式，能否得到正确的解，同样具有随机性。因而在理论上说明不了什么。本人的子句消去法可以清楚地告诉人们，什么情况下SAT有解，什么情况下无解，而且会准确地说出解的数量。国外搞得SAT竞赛，据说每年一次。这种竞赛在没有理论保证的情况下，应该说只是一种游戏而已。如果他们能够认识到我创造的理论的正确性，这种游戏就该结束了。从这方面看，我的研究倒有点罪过了。。。

SAT问题的解决，据说涉及众多方面，但我感到最重要直接的是集成电路优化、可靠性检测，这涉及到信息产品的效率、速度、可靠性、安全性。未来设计的超大规模集成电路系统，不会发生未知原因的死机，也不用设计那种“看门狗”之类的东西。如果集成电路运行状态都在我们的掌控之中，在相互比拼的决战中，不出状况，岂不是会高人一头？用在国防战场方面，意义之重大可想而知！

不怕讽刺挖苦，科研需要有坚韧不拔的精神，成功就属于你。当然，这一切需要你有雄厚的根基，渊博的知识和勇于探索的底气。

为了纪念我实际设计求解3-SAT满足解和全解的程序的完工和测试，特此写字。

2017-5-1