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

博文

NP是可计算的吗?- 常量与变量关系中的认知层次问题

已有 3388 次阅读 2015-1-9 14:14 |个人分类:不确定性问题和算法讨论|系统分类:论文交流| NP问题, 不确定性的消失

网友姜咏江的博文“美国克雷数学研究所会不会颁奖?http://blog.sciencenet.cn/home.php?mod=space&uid=340399&do=blog&id=849311”,通过辨析常量与变量不同,说明NP问题定义的流行观念中可能存在着的悖论。

此文涉及到二个常见的算法问题:

1,搜索问题(http://zh.wikipedia.org/zh/計算複雜性理論):任给一个集合A,和一个数a,问a是否在A中?

2,子集元素和问题(http://zh.wikipedia.org/wiki/子集合加總問題):任给一个整数集合,问是否存在某个非空子集,使得子集元素和为0?例:给定集合{−7, −3, −2, 5, 8},答案是yes,因为子集{−3, −2, 5}的数字和是0。

“搜索问题”是常见的P问题,任给一个元素个数为n的集合A,及一个数a,最多比较n次,即可判定a是否在A中。故“搜索问题”存在着多项式时间复杂度O(n)的算法。

“子集元素和问题”是常见NP问题,任给一个k个整数的集合,至今未找到多项式时间复杂度算法,只有基于枚举的指数时间算法。

网友姜咏江视角独特,从“搜索问题”的角度,追究“子集元素和问题”:“给定k个数组成的集合,求其全部非空子集。我们都知道子集数应为2k-1。子集元素和最多有多少?最多也就是这2k-1个。现在我们要给出一个数a,问a是否在这2k-1个和数当中,验证的时间复杂度是多少?是O(2k)还是O(n)?在这个问题中,k是一个常量,莫要将其当成变量来看。用变量表达式来研究程序执行时间复杂度,必须要加以严格区分变量和常量。问题的正确答案应该说是O(n)。”

网友姜咏江的文章正确地指出,将常量2k一般化为变量2k,是问题的关键。我们认为,这是流行的NP问题理论中一个最常见、最隐蔽、最顽固的认知错误。在认识论上,是“个别问题”与“一般问题”的混淆,在哲学上有深远的根源。

流行NP问题定义,是基于指数时间的枚举算法来定义的(对此话题,大家还可参见“未來數學家的挑戰 http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html)”,然而,此枚举算法针对的却是“搜索问题”,“搜索问题”实际上又是多项式时间复杂度O(n)可求解的P问题!也就是说,流行的NP问题的定义,暗中将NP问题定义成了P问题,从而混淆了NP问题与P问题的层次,使真正的NP——不确定性消失了。“不确定性的消失”,正是我们长时期通过对库克的原初论文深入研究,所得到的一般性结论,现在贴出另一篇论文“What is Cook's theorem?”  



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

上一篇:“判断”的层次
下一篇:什么是Cook's Theorem?
收藏 IP: 82.246.87.*| 热度|

2 姜咏江 icgwang

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

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

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

GMT+8, 2024-3-29 13:13

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部