我为什么敢说解决了P与NP问题？

姜咏江

   P/NP问题号称世界第一难题，我有什么底气敢说自己解决了这个问题，敢作出P=NP的结论？理由很简单。

1.              设计出了通用子集和软件

   关于子集和问题的学术地位，在Introduction Algorithms这本书的1078页有介绍（见图1）。

图1  子集和问题的学术地位

将图3中标注部分翻译成中文：34.4节和34.5节中完全性证明的结构，所有的证明都是通过对CIRCUIT-SAT的NP完全性归约得到的。

   据说图3这棵树分支上的任何一个问题都是NPC问题，任意一个NPC如果找到了通用的解法，并且是多项式时间内完成的，那么就可以下结论：P=NPC，即有P=NP。

   我设计的BuildSubset_Sum软件可以完成对任意有限整数集（可以在数的定义上加上小数）的子集求和。例如图2，用菜单BuildSet/CreateSet随便输入17个数（几个都可以），就可以在程序出现ok！之后通过GuessCheck菜单输入任意整数，就可以找满足条件的子集。如果有，系统就会列出来，没有会显示没有的提示。

图2  子集和软件使用

2.              多项式时间复杂度

   我们已经设计出了满足要求的子集和程序，但这个程序是否满足所谓多项式时间复杂度？这个问题需要分为两部分来考虑。

2.1         建立全部子集时间

   给定n个数形成的集合，它的子集共有2ⁿ个，这是人们都知道的。问题是这2ⁿ个子集能够一一建立起来吗？建立的程序运行时间如何表示出来？这与选择什么样的算法来设计程序有很大关系。子集和subset_sum问题可以如下描述：

   设n元数集A={ x₁,x₂,x₃,....,x_n }，y是某给定的数，求BA，B的元素和为y。

对于象n元的subset_sum这种函数，表面上看可以用下面的（1）式简单表达，可实际上解起来十分困难。

       y=a₁x₁+a₂x₂+a₃x₃+....+a_nx_n                       （1）

其中a_i值为0或1，i =1,2,...,n。由于我们探讨的是有限集合，而且集合不允许出现重复元素，所以还必须设定，当i≠j时，则x_i≠x_j。

   由于x_i并不是有规律变化的，并且n的值并不确定，所以用（1）式难以准确计算。如果采用循环取值并判定a_i值是否为0，这样循环的次数会接近nⁿ，可见计算起来将会多费时间。如果将x_i由小到大排列起来，也需要接近n！次循环。由此可见，用公式（1）进行计算并不是好方法（参阅http://blog.sciencenet.cn/blog-340399-849597.html）。

   关于子集和问题，我已经在几个月前设计出了用添加元素的方法，逐一得到所有子集的算法程序，其要点是从空集开始，每增加一个数，都将原有的所有子集添加上这个数，这样就得到了新增加后的全部子集，并在新子集中确定是否存在满足要求的集合（该程序方法我已经公布在科学网的博客http://blog.sciencenet.cn/blog-340399-849040.html中）。这个问题每增加一个数，那么子集数就会增加一倍。因为n个数的子集共有2ⁿ个，当n变为n+1时，子集数就到了2ⁿ⁺¹=2×2ⁿ个。

   用公式（1）方法设计程序，就要形成将形成n层n次循环嵌套；用元素添加方法设计程序，就形成了2ⁿ次循环操作调用。这说明采用不同的算法，即使是相同的输入也会直接影响到了循环嵌套的层次数及循环次数。

2.2         子集和的判定时间

   因为算法时间复杂度涉及到时间问题，这里我们自然要问：“建立有限集的全部子集要用多少时间？”

我为了读者易懂，这里采用非计算机专业化的叙述。

如果假设每添加一个元素所需的时间相同，于是得到n个元素的全部子集所需时间应是t=2+2²+…+2ⁿ

由于n是有限整数，故得到全部子集所需时间t就是一个多项式时间。

   剩下来的问题：如果要查找子集和是否是给定的数需要多少时间呢？

   我们假定n个数的加法用一个单位时间，不妨就设是添加元素操作的a倍，那么2ⁿ个子集求和与比对给出的数，也不会超过a2ⁿ个单位时间。

   这样在即使没有建立子集的情况下，判定一个数会不会是某个数集的子集和，也不过要用2+2²+…+2ⁿ+a2ⁿ个单位时间而已。

3.              算法时间复杂度的大o表示不靠谱

   关于用多项式最高阶项来确定算法时间复杂度的不靠谱，我们来举一个例子。一个算法的时间如果是一个多项式1²+2²+3²+...+ n²所表示的，那么前n-1项和与第n项之差为：

S_n-1- n²=1²+2²+3²+...+(n-1)² - n²=1²+2²+3²+...+1+ ( n-2)² -2n，

由此可知，当n>4时，就有S_n-1- n² > 0。由此可见，只用多项式的最高阶项说明算法时间复杂度的误差有多大。

   有人说O(n^k)和O(cⁿ)大不相同，其实可以将O(n^k)变成O(10^km)，m也是一个整数变量。可见O(n^k)和O(cⁿ)并无本质不同（见http://blog.sciencenet.cn/blog-340399-898296.html）。

4.              结论

   所谓的算法多项式是由多个只有乘法运算的项（包括整数幂）求和的表达式组成的。例如

等都叫多项式，它们之间可以相互转换。

在此多项式意义之下P=NP。

为解答网友对2+2²+…+2ⁿ的认识，补充：

 t=2+2²+…+2ⁿ=11....10 是一个n+1位的二进制数。于是所谓O(2ⁿ)就是O(t)。这是将所谓指数多项式转为底数多项式的一个例子。

子集和问题软件下载：BuildSubset_Sum.rar

2015-06-23