P = NP 的一个简单论证

 

         各位XDJM、FLXQ …… 大家都辛苦了。

 

         好的开始是成功的一半。

 

         预祝各位新年新气象，为那个不愿意有，最终也确实好像没有到来的末日2012画个舒心的句号吧。

 

         闲言少叙，书归正传。

     P,NP一直是计算领域的麻烦事，好多人都相信P ≠NP，典型的西方逻辑思维，批判多次了，不想再说了。

 

       现在以 SAT 问题为例，讨论一下P = NP问题。

        SAT问题也称为合取范式的可满足问题，一个合取范式形如下：A₁∧A₂∧…∧A_n，

    其中，子句A_i（1≤i≤n）形如：a₁∨a₂∨…∨a_k，

其中，a_i称为文字，为某一布尔变量或该布尔变量的非。

 

         SAT问题是指：是否存在一组对所有布尔变量的赋值（TRUE或FALSE），使得整个合取范式取值为真。

 

论证如下：

         首先给出极大项的概念，含有k个布尔变量的简单析取式，若任意一个布尔变量的它的否定不同时出现，而两者之一必出现且仅出现一次，且第i个变量或它的否定出现在从左起的第i位（这里假定布尔变量有一个预定的排序方案），称这样的简单析取式为极大项。

         易知，k个变量的可以产生P(P=2^k)个不同的极大项,其中,每个极大项有且仅有一个成假赋值，现在把第i个极大项的成假赋值

对应的二进制数记作M_i。

         现在构造一个映射函数F，使得每个极大项对应有一个函数值，表达式为：

         F(i) = ~ 2^(M_i⁾;

 

         根据映射函数F，

         可以解出k个变量的函数值G(i)如下：

         G(i) 的二进制表达式是一个长度为P循环字符串T(m)，该字符串的循环节是2^(k+1-i),

 

在每个循环节内，有如下表达式：

 

① 若0≤m ＜2^(k-i) ，T(m) = 0;

② 若P＞m ≥2^(k-i)， T(m) = 1;

 

         至此，

         把G(i)代入任意一个合取范式A₁∧A₂∧…∧A_n ，

如果结果为0，则合取范式不可满足；

若结果非0，则合取范式是可满足的。

        

         现在，已经把合取范式的判断问题转换为一个简单的数值计算问题。

 

注意，

         我们实际上并不需要把每个G(i)代入合取范式计算（当然，在k比较小的时候，这也是一个比较快速的算法）。

 

         我们真正需要的是T(m)的表达式的计算问题，

         即对于析取子句A_i，先计算A_i的值为1的表达式L(A_i)；

         然后，

         对于整个合取范式，我们再判断L(A_i) = 1 是否存在重叠位即可。

         好了，终于摆脱了搜索的困境

         #######################################  

 

以三个变量a₁,a₂,a₃为例，函数赋值如下：

 

 

其中每个变量的函数值如下：

 

 

 

更加严格的叙述（或者说，如果还需要的话），改天再整理一下，欢迎砖头……

 

……饿呀，先吃饭去了。

转载本文请联系原作者获取授权，同时请注明本文来自刘超科学网博客。
链接地址：https://blog.sciencenet.cn/blog-618605-648534.html

上一篇：个人信息资源管理
下一篇：一个回帖