NPC=P

姜咏江

我说过，“搞创新科学研究就如同坐过山车。”在设计3-SAT问题求满足解程序的过程中，又让我坐了一次过山车。在用子句消去法求出联想的满足解，最后遇到了全是孤立变量的情况，而且孤立变量形成的3-SAT也可以无解！这是我先前没有深入思考的。

经过一个多月的深入研究，变换思路，引进了“可无解块”和“可无解表”。一切问题就迎刃而解了。再次验证了限位数理论的重要性。可以肯定，子句消去法的算法时间复杂度不会超过O(n⁴) 。如果谁要是说P≠NP，我一定要与他有一场论争。

其实，3-SAT有许多有利于指数时间DPLL的合取范式，也有许多有利于多项式时间算法的子句消去法的合取范式，个别例子求解的速度很快，不能说明问题，只有所有的情况都考虑在内，才能够得到最终的结论。

2017-10-22