CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

P vs. NP 问题的总结

已有 808 次阅读 2019-12-27 05:33 |个人分类:P/NP问题|系统分类:科研笔记| 仿量子计算机, SAT, 多项式

姜咏江         accsys@126.com

    2016年我在科学网上发表了《多项式时间复杂度和指数时间复杂度相差多少?》的博文,设计了仿量子计算机之后,才敢肯定此那里结论的正确性。现将原文再次贴到本文的后面,作为4年之后的进一步肯定。

学界早已认可,只要NP-completeSAT问题是P问题,那么就有P=NP。我开始认为P=NP。搞了仿量子计算机之后,最终认定了这是一个具有相对性问题。问题的关键是多项式时间和指数时间复杂度的区分问题。从Cn0+Cn1+...+Cnk-1+Cnk+...+Cnn =2n这个公式可知,只要表达式的幂指数最高k为小于n的常数,那么Cn0+Cn1+...+Cnk-1+Cnk就是多项式,不然就是一个指数函数的表达式。这样,计算机算法的操作步骤符合多项式,那就是P类问题,不然就是NP类问题。显然,我们如果能够一次计算2n个数,那么所谓的NP类问题就不复存在了。这就是量子计算机或仿量子计算机要做的事情。

具体到SAT问题,转化成01表的形式,那么最多会有2n个子句。问题本身的子句数m如果随着n变大而变大,也就是找不到确定的常数k,那就是一个n的指数时间复杂度算法问题。但一次能够实现一个子句与2nn位二进制数计算,那就转化成了子句数变量m的多项式时间复杂度算法。

 

附录:

多项式时间复杂度和指数时间复杂度相差多少?

姜咏江

如果以问题条件中对象数量n做为考察标准,随着n的增大,什么样的算法耗时增长速度快?这就是解题当中的时间复杂度问题。同一个问题,寻找耗时增长速度最慢的算法,无疑具有十分重要的意义。

从数学知识知道,一次函数y=an+b随着n的变大,y的增长速度是不变的。还知道,kc是大于1的常正整数时,y=a0n0+ a1n1+ ...+aknkz=a0c0+ a1c1+ ...+an-1cn-1+ancn比较,当n大到一定程度后,z的增长速度要比y快得多。y的表达式称为多项式型,z的表达式称为指数型。

在计算机编程的算法中,如果对n的重复操作是可以用多项式型计算,避开指数型无疑是人们所希望的。在计算机中对n的重复操作是可以用多项式型计算就是多项式时间复杂度O(nk),用指数型计算的过程,就是指数时间复杂度O(cn)。有许多实际问题,人们只是找到了指数型的算法,没有找到多项式型算法。对于后者能否找到多项式型算法的研究成为了世界难题,这就是PNP问题。

指数型最简单的是z=2n。我这里就举求集合子集的例子,来说明这两者的关系。

A. n个元素集合的全部子集数。

用元素添加法,包括空集有Cn0+Cn1+...+Cnn=2n.

B. n个元素集合的不超过3个元素的子集数。

同样用元素添加法,包括空集有Cn0+Cn1+...+Cn3.

由此可见多项式型和指数型之间的关系。多项式型的幂指数一定是不超过一个常数,这是二者区别的关键。在n增大的时侯,k是不能够也跟着n增大。很多人混淆了这种约定,因而陷入了无法自拔的境地。

不可否认,在k相当大的时侯,随着n的增大,用计算机计算仍然耗时庞大,但与指数型最小的2n比起来也会是“小巫见大巫”。

 

证明Cn0+Cn1+...+Cnn=2n如下:

添右定理n元集合用添右组合法得到全部非空子集为2n-1个。

这个定理需要证明全部非空子集不少,且都不相同。

这里用归纳法来证明。

n=2,那么A=a1,a2},则A的转移组合得到的子集为{a1}{a2}{a1,a2}子集数为22-1=3说明子集数正好且不重复。

n=k时得到的子集{a1}{a2...a1,a2,...,ak}满足条件子集数为2k-1,且不重复。那么当n=k+1时,则除添加子集{ak+1}之外,需要将n=k时得到2k-1个子集全部添加ak+1,形成的全部子集为

a1}{a2...ak}{ak+1...a1,a2,...,ak}{a1,a2,...,ak,ak+1

子集总数应为2k-1+2k=2×2k-1=2k+1-1,说明子集总数正确。

假设n=k+1时出现了重复子集,不妨设有子集Bi=Bjij,它们之中都包含ak+1。那么将ak+1从它们之中取出,则应有Bi\ak+1=Bj\ak+1},这与n=k时得到的子集不重复子集矛盾。故没有重复子集产生。

证毕。

 

 

2016-12-1

 

 

 

 

 

 




http://blog.sciencenet.cn/blog-340399-1211643.html

上一篇:没有留学国外的经历就没有重大发明?
下一篇:限位数理论是机器计算的基石

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-30 00:15

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部