不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

解读关于“多项式时间”的一个悖论

已有 4181 次阅读 2015-9-2 11:33 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 悖论, versus

网友们敏锐察觉到对“多项式时间”的解读是探讨“P versus NP”的一个重要议题,为此谈及一个旨在解读“多项式时间”的表达式(注):

- 2^n=Cn,0+Cn,1+Cn,2+Cn,3+…+ Cn,n-1+ Cn,n

一方面,从组合数计数公式Cn,k=n(n-1)(n-2)…(n-k+1)/k!来看,Cn,k是一个k次多项式,其中k≤n,等式的右边是多项式,而等式的左边是指数型,故有:指数型函数与多项式函数相同。另一方面,于算法的一般性质,指数型时间复杂度的算法与多项式时间复杂度的算法又不同,故网友们认为,此等式隐含着“悖论”。

为了方便分析此“悖论”,我们构造另外一个更容易分析的表达式:

-2*n = 2+2+…+2,即n个2的加法,可表达为2乘n。

实际上,这个表达式涉及到两个观点:一是人的认知,二是算法(数学式)。

作为人的认知,这个表达式可看成是一个命题,其意义是:人认为,2*n = 2+2+…+2这个式子揭示了——“乘法”是人对加法(算法)的抽象,这是一个关于事实的本质的陈述,是认知层次上的。

在算法层次上,2*n = 2+2+…+2表达的是算法。人做乘法只有两个工具,背九九乘法表,或者,将乘法转化为加法由计算工具执行。我们知道,在具体的计算机CPU硬件中,所有的计算都是由加法器完成的,就是说,计算机本质上只是一个加法器,计算机永远只能做加法,通过编程,机器才能做乘法,所以2*n = 2+2+…+2表达的是转化关系,也就是机器如何以加法器执行乘法。在这个意义上,2*n = 2+2+…+2不过也就是P=P。

但是,若把算法层次混入到认知层次,这个表达式就成了“悖论”,即于算法意义上得出:“乘法=加法”,由此悖论推出,计算机本质是乘法器,即具有加法并行能力,是本质上的并行计算机,也相当于具有计算NP的指数时间能力的“神喻机”了。

悖论产生于兩个不同层次的混淆,但若将两个层次清楚分开,悖论就不悖了。用同样的方法也可以分析网友们提出的表达式“2^n=Cn,0+Cn,1+Cn,2+Cn,3+…+ Cn,n-1+ Cn,n”所隐含的“悖论”。

“白马非马”揭示了相同的意义,当把公孙龙与卫兵的立场分开,“白马非马”就不矛盾了,“悖论”非悖也!

注:

-多项式型与指数型算法悖论(http://blog.sciencenet.cn/blog-340399-907226.html

-P≠NP——基于认知的视角(http://blog.sciencenet.cn/home.php?mod=space&uid=2446134&do=blog&id=914263




https://wap.sciencenet.cn/blog-2322490-917832.html

上一篇:世纪难题“P versus NP ”与金融市场的不确定性
下一篇:对“多项式时间复杂度”的误解
收藏 IP: 82.246.87.*| 热度|

1 杨正瓴

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

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

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

GMT+8, 2024-11-1 07:40

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部