|||
网友姜咏江的博文“美国克雷数学研究所会不会颁奖?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?”
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-20 02:48
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社