谁说P≠NP？

姜咏江

   据说世界头号难题P/NP问题，最后落实到NPC问题是否是P问题上？依据斯提芬.库克的理论，又落实到3-CNF-SAT这个NPC问题是否是P问题上。直至今日，世界上尚未见到有人能够明确地指出3-CNF-SAT是否是P问题。

   本文作者经过较长时间的研究，对NPC问题k-CNF-SAT创造性地提出了消去法求解的简捷方法（见http://blog.sciencenet.cn/blog-340399-901277.html ），并指出k阶合取范式f(x₁,…,x_n)的子句最多数量，从而可以明确地证明k-CNF-SAT求解的时间复杂度是一个多项式时间O(n^k)。这就简单地证明了P=NP！

下面就是通俗简单的证明。

1.              k-CNF-SAT的子句最多有C_2n^k个

       n个逻辑变量所成的k阶合取范式最多有多少个子句？在合取范式子句中仅可以出现变量与其非的表示。我们将逻辑变量和这个变量的非分别用x与x’表示，那么n个逻辑变量所成的k阶合取范式子句数，就是从2n个元素中取出k个的组合数C_2n^k。

例如，n=3，k=2时的合取范式2-CNF-SAT子句最多有C_2n^k=15:

f(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₂’) (x₂’+x₃) (x₁+x₃’) (x₂+x₃’).

2.              消去法求解k-CNF-SAT的时间复杂度为O(n^k)

由于k-CNF-SAT子句最多有C_2n^k个，所以用消去法确定f(x₁,…,x_n)=1的解，每次操作至少消去1个子句。因而，求解过程最多操作不超过C_2n^k次，而C_2n^k=2n (2n-1)…(2n-k+1)/k!，这是一个k次多项式。于是按照所谓的算法时间复杂度的大O表示法，求解合取范式k-CNF-SAT的f(x₁,…,x_n)=1的解是一个多项式时间，即可以用O(n^k)来表示。

友情提示：引用请注明出处（盗用必究）。Email: accsys@126.com

2015-7-1