姜咏江         accsys@126.com

    2016年我在科学网上发表了《多项式时间复杂度和指数时间复杂度相差多少？》的博文，设计了仿量子计算机之后，才敢肯定此那里结论的正确性。现将原文再次贴到本文的后面，作为4年之后的进一步肯定。

学界早已认可，只要NP-complete的SAT问题是P问题，那么就有P=NP。我开始认为P=NP。搞了仿量子计算机之后，最终认定了这是一个具有相对性问题。问题的关键是多项式时间和指数时间复杂度的区分问题。从C_n⁰+C_n¹+...+C_n^k-1+C_n^k+...+C_nⁿ =2ⁿ这个公式可知，只要表达式的幂指数最高k为小于n的常数，那么C_n⁰+C_n¹+...+C_n^k-1+C_n^k就是多项式，不然就是一个指数函数的表达式。这样，计算机算法的操作步骤符合多项式，那就是P类问题，不然就是NP类问题。显然，我们如果能够一次计算2ⁿ个数，那么所谓的NP类问题就不复存在了。这就是量子计算机或仿量子计算机要做的事情。

具体到SAT问题，转化成0和1表的形式，那么最多会有2ⁿ个子句。问题本身的子句数m如果随着n变大而变大，也就是找不到确定的常数k，那就是一个n的指数时间复杂度算法问题。但一次能够实现一个子句与2ⁿ个n位二进制数计算，那就转化成了子句数变量m的多项式时间复杂度算法。

附录：

多项式时间复杂度和指数时间复杂度相差多少？

姜咏江

如果以问题条件中对象数量n做为考察标准，随着n的增大，什么样的算法耗时增长速度快？这就是解题当中的时间复杂度问题。同一个问题，寻找耗时增长速度最慢的算法，无疑具有十分重要的意义。

从数学知识知道，一次函数y=an+b随着n的变大，y的增长速度是不变的。还知道，k和c是大于1的常正整数时，y=a₀n⁰+ a₁n¹+ ...+a_kn^k和z=a₀c⁰+ a₁c¹+ ...+a_n-1c^n-1+a_ncⁿ比较，当n大到一定程度后，z的增长速度要比y快得多。y的表达式称为多项式型，z的表达式称为指数型。

在计算机编程的算法中，如果对n的重复操作是可以用多项式型计算，避开指数型无疑是人们所希望的。在计算机中对n的重复操作是可以用多项式型计算就是多项式时间复杂度O(n^k)，用指数型计算的过程，就是指数时间复杂度O(cⁿ)。有许多实际问题，人们只是找到了指数型的算法，没有找到多项式型算法。对于后者能否找到多项式型算法的研究成为了世界难题，这就是P与NP问题。

指数型最简单的是z=2ⁿ。我这里就举求集合子集的例子，来说明这两者的关系。

A. 求n个元素集合的全部子集数。

用元素添加法，包括空集有C_n⁰+C_n¹+...+C_nⁿ=2ⁿ.

B. 求n个元素集合的不超过3个元素的子集数。

同样用元素添加法，包括空集有C_n⁰+C_n¹+...+C_n³.

由此可见多项式型和指数型之间的关系。多项式型的幂指数一定是不超过一个常数，这是二者区别的关键。在n增大的时侯，k是不能够也跟着n增大。很多人混淆了这种约定，因而陷入了无法自拔的境地。

不可否认，在k相当大的时侯，随着n的增大，用计算机计算仍然耗时庞大，但与指数型最小的2ⁿ比起来也会是“小巫见大巫”。

证明C_n⁰+C_n¹+...+C_nⁿ=2ⁿ如下：

添右定理：n元集合用添右组合法得到全部非空子集为2ⁿ-1个。

这个定理需要证明全部非空子集不少，且都不相同。

这里用归纳法来证明。

设n=2，那么A=｛a₁,a₂｝，则A的转移组合得到的子集为｛a₁｝｛a₂｝｛a₁,a₂｝子集数为2²-1=3说明子集数正好且不重复。

设n=k时得到的子集｛a₁｝｛a₂｝...｛a₁,a₂,...,a_k｝满足条件子集数为2^k-1，且不重复。那么当n=k+1时，则除添加子集｛a_k+1｝之外，需要将n=k时得到2^k-1个子集全部添加a_k+1，形成的全部子集为

｛a₁｝｛a2｝...｛a_k｝｛a_k+1｝...｛a₁,a₂,...,a_k｝｛a₁,a₂,...,a_k,a_k+1｝

子集总数应为2^k-1+2^k=2×2^k-1=2^k+1-1,说明子集总数正确。

假设n=k+1时出现了重复子集，不妨设有子集B_i=B_j，i≠j，它们之中都包含a_k+1。那么将a_k+1从它们之中取出，则应有B_i\｛a_k+1｝=B_j\｛a_k+1｝，这与n=k时得到的子集不重复子集矛盾。故没有重复子集产生。

证毕。

2016-12-1