P与NP问题是让聪明人做傻事

姜咏江

   世界上的事情有难有易，这是人们都知道的常识。然而就是被称为世界上的聪明人常常做傻事。上中学时听说过：牛顿在门上挖一个大洞和一个小洞，为的是让小猫走小洞，大猫走大洞。这事真假且不论，反映出聪明的科学家也可能办傻事。

   千禧大奖的头号世界难题，P/NP问题就是一个让聪明人办傻事的闹剧。为什么？这事是让人们将所有的复杂的事情都去找简单的方法解决同一件事情的全部结果混为了一谈。我以解决任意N个数的子集和问题为例，就可以说明这种混淆给人们带来的艰苦劳动是多么的不值得。

      N个元素集合每增加一个元素，那么就要增加2^N个子集，这就是说在不知道子集都是什么的情况下，需要以指数运算的方式来求这些子集，这在算法执行中自然要消耗大量的时间。如果我们将这一过程做为查找某个满足条件的子集是否存在（yes/no问题），那么就不可能是一种较快执行的算法。如果我们在N个元素集合的所有子集都存在的情况下，去回答某个满足条件的子集是否存在的yes/no问题，我们只要用查询的方法就可以完成，也就是说我们可以用O（n）的所谓多项式时间复杂度解决问题，也就可以得出P=NP的结论。

   因为求子集的算法是一个指数型运算过程，这个问题不可能用n^k形式的算法（k是常数）求解全部子集。即使某个曾经认为复杂的问题能够用简单的函数问题求解，也不代表能够将所有复杂的问题都可以用简单的固定多项式函数方式得到yes/no问题的回答。

   我在这里规劝那些科学界的聪明人莫要再为这种傻事浪费时间了。请参考

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

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

2015-5-1