许多资料在讨论N=NP?这个问题的时候并没有抓到这个问题实质,而主要是将其看成一个“理论”的甚至跟软件工程毫不相干的东西。许多人的经验可能都会告诉他们这个问题“没用”,但实际上我们也可以看到,这些人其实通常都是用某种“事实论证”来近似化这个问题,甚至很多专门做计算理论的“教授”其实也是如此。我们活在一个依靠经验而被推向主观主义的时代,这些论调可以说是一点也没懂。
——越是不懂的东西,我们就越爱把他们抽象化,这大概是我们中国人的一种病了。
第一个问题是我们需要明白所谓的“问题类”是什么意思。通常的教说是从“问题的集合”来切入的。如果我们把集合看成高中课堂上说成的“确定的东西的封闭组合”,我们可能马上就会对N=NP?产生一种满足感,可惜这个理解是错的。
集合的语言允许许多并未发生的东西。例如我们考虑集合 S = { 明天打伞的人 }。实际上如果明天打伞的人还不存在一个规律,或者说我们总之不可能确定,那么这个集合 S 是不是确定的呢?
现在我们尝试考虑一下一个可能更宽泛的集合 T = { 明天会出现的问题 } 。很显然这个集合出现了跟集合 S 类似的困难。
然后我们考虑这个问题,假如 Q = { 所有的问题 } 。由于一些集合论本身的缺陷,Q可能本来就是一个不可能的概念。但我们先不考虑这个问题,我们先考虑 T 是 Q 的子集?
显然,所有的问题包括明天的问题,也包括昨天的问题、今天的问题甚至是与时间无关的问题。由此我们可以看到,要抽象地讨论“问题类”,并不是一个容易的事情,除非我们想做的是“分析哲学”。
明天我们可能都不能知道,我们又如何讨论“所有的问题?”。现在我们看到了“问题类”本身的困难:一种绝对唯理论的困难。但幸运的是,计算机科学家不是要做“分析哲学”,相反的,问题提出的是:P时间复杂度可以解决的问题。
这意味着什么?这意味着我们讨论非量子计算机(决定图灵机)等等意义上的运算能力的极限下,计算机到底能做的计算的那个集合。
第二问题是我们我们理解所谓的“问题”。我们要注意,P=NP?所谓的“问题”,并不是!!!具体的问题,而是一个实用主义的意义上的用法。所以,这个问题,就是计算机的任务,就是计算机所发挥的作用,就是计算机所可以去解决的一切,就是计算机所能处理的世界。
简单地,我们如果用“世界观”的说法来说 N=NP? ,那么 N=NP? 其实是这样一个问题: P 复杂度的世界和 NP 复杂度的世界是否是同一个世界,或者不是同一个世界,或者别的什么可能?证明。
今天的软件工程仍然要解决“问题”。但通过模块化,组件,协议,统计学,计算机和其他领域的交叉,许多“问题”已经解决了,哪怕他们并不成为一个理论。而计算机如果还在实践,我们似乎就应该期待“问题”也不是一成不变的。而N=NP?把这种思路颠倒过来了:P 复杂度的世界和 NP 复杂度的世界是否是同一个世界?
在这个意义上,我们可能不能马上给出答案,但这个问题至少指向这样一个鸿沟: 假如我们承认世界的复杂性至少可以分为 P 和 NP ,在 N复杂度的世界 和 NP复杂度的世界 之间是否有着一道鸿沟?还是没有鸿沟?
如果我们把N复杂度的算法叫做“快”的算法,NP复杂度的算法叫做“能”的算法,N=NP? 就会变成: (就通过编程图灵机,进而由图灵机自动解决问题的意义上) 图灵机的快,和图灵机的能,是不是一回事?这甚至还需要物理学的发展。
这个问题当然不会马上变成“软件工程”,但无疑是我们对“软件工程”“软件”所能够真正发展,就其可以理解为“组合物”的意义上,其客观的情况是如何?这的确是十分致命的。
--
修改:darkk FROM 223.72.41.*
FROM 223.104.38.*