美国克雷数学研究所会不会颁奖？

                        姜咏江

      千禧年大奖难题(Millennium Prize Problems), 又称世界七大数学难题， 是七个由美国克雷数学研究所(Clay Mathematics Institute,CMI) 于2000年5月24日公布的数学猜想。根据克雷数学研究所订定的规则，任何一个猜想的解答，只要发表在数学期刊上，并经过两年的验证期，解决者就会被颁发一百万美元奖金。这些难题是呼应1900年德国数学家大卫·希尔伯特在巴黎提出的23个数学问题。

   上面这段话是从《百度》上复制下来的。CMI的悬赏很有诱惑力。就pnp问题来说，CMI会不会颁奖呢？我的回答是不一定。为什么呢？我就最近设计的subset_Sum软件来说一下理由。

   有一个元素个数为2100的整数集合，要查找某数a在不在其中，请问查找的时间复杂度应是多少？我们可以设一个变量xn，承载这2100个数，则n=1,2,...,2100。那么找到a的比较次数应不超过2100-1次吧？用n来表示呢？那就是n-1次而已。看来这无疑是一个多项式时间复杂度的问题。

   现在我们来说，给定k个数组成的集合，求其全部非空子集。我们都知道子集数应为2k-1。子集元素和最多有多少？最多也就是这2k-1个。现在我们要给出一个数a，问a是否在这2k-1个和数当中，验证的时间复杂度是多少？是O(2k)还是O(n)？

   在这个问题中，k是一个常量，莫要将其当成变量来看。用变量表达式来研究程序执行时间复杂度，必须要加以严格区分变量和常量。问题的正确答案应该说是O(n)。由此来看，程序执行时间复杂度问题与变量取值即定义域无关。莫把变量的取值范围与程序执行时间复杂度混为一谈，不然将出现悖论。

   任意一个n元数构成的集合，其非空子集为2n-1个。这是说n一旦确定，那么2n-1就是一个确定的数；当n是变量的时候，你不能确定2n-1比100大还是小。变量和常量是一对相互对立的概念，凡是混淆了对立概念，把它们放到一起等同来看的时候，都会产生悖论，这是悖论产生的一种普遍现象。

   因而我们应该得出结论：任何在数集上查找一个数的过程都是具有多项式时间复杂度O(n)的过程。

   我在前面博文中提出了一个比较公理。Subset_sum问题中，如果将确定的子集数2n-1又做为变量来研究，那就违背了比较公理，也违背了Subset_sum问题的基本涵义。

   CMI如果明确了这个问题，那么他才会有颁奖之日，否则无日可待。

又对Subset_sum问题的软件进行了修理。大家可以见到在集合确定的情况下，查找一个子集和猜测验证一个数是不是某些子集的元素和，同样都可以快速地完成。由于每人计算机的存储资源不同，该软件的运行数据范围会有区别。

   特将最后整理的软件附上，内有使用说明书，供有心人参考。

2014-12-8

BuidSubset_Sum.rar