P≠NP——基于认知的视角

（xbdxzwm@163.com）

   之前我写了一篇关于P vs. NP问题的文章整理了对于这个问题的一些认识，现在我再进一步把我的认识写的更清楚一些，与各位同行交流。文章证明并不复杂，而且还比较有趣，它不仅是一个数学证明，更牵扯到了人们的基本认知。欢迎各位前辈同行的宝贵意见啊！

摘  要 

   我们从多项式函数的加法运算的角度讨论 $P vs. NP$ 问题。在 $k(\leq n)$ 个关于 $n$ 的多项式的和总是一个关于 $n$ 的多项式的命题下，我们构造出了一个悖论；而在存在某 $k(\leq n)$ 个关于 $n$ 的多项式的和为关于 $n$ 的指数函数的命题下，我们很容易证明了 $P\neq NP$ 。

1 预备工作

1.1 二项式定理的两个性质

在给出证明之前，我们先来回忆一下二项式定理（或杨辉三角）：

$(a+b)^{n}=C_n^0a^n+C_n^1a^{n-1}b+C_n^2a^{n-2}b^2+\cdots+C_n^{n-1}ab^{n-1}+C_n^nb^n$ ，

其中， $C_n^k=\frac{n!}{k!(n-k)!}$ 。

我们有下面的引理：

引理 1. 设 $n$ 为任意的偶数，则 $C_n^{n/2}$ ≥ $\sqrt{2}^n$ 。

证明： $C_n^{n/2}=\frac{n!}{\frac{n}{2}!\frac{n}{2}!}=\frac{n\cdot(n-1)\cdots (n/2+1)}{n/2\cdot (n/2-1)\cdots 1}\geq 2^{\frac{n}{2}}=\sqrt{2}^n$ 。

引理 2  对于任意的整数 $k$ ， $n$ ， ( $1\leq k\leq n-1$ )，我们有 $C_n^{k+1}=C_{k}^k+C_{k+1}^k+\cdots+C_{n-1}^k$ 。

   证明：注意到 $C_n^{k+1}=C_{n-1}^{k}+C_{n-1}^{k+1}=C_{n-1}^{k}+(C_{n-2}^{k}+C_{n-2}^{k+1})=$ $\cdots=C_{n-1}^k+C_{n-2}^k+\cdots+$ $(C_{k+1}^k+C_{k+1}^{k+1})$ 及 $C_{k+1}^{k+1}=C_{k}^k$ ，引理得证。

1.2 一个经验公理

   下面我们给出一个经验公理。

公理 1 设 $F(n)=a_0+a_1n+\cdots+a_mn^m$ 为任意一个关于 $n$ 的多项式函数， $G(n)=b_0b_1^n$ 为任意一个关于 $n$ 的指数函数，且 $b_0>0$ ， $b_1>1$ 。则 $\lim\limits_{n\rightarrow \infty}\frac{F(n)}{G(n)}=0$ 。

    公理1的说的是当 $n$ 足够大时，多项式函数与指数函数相比是小到可以被忽略的。有的学者认为这本来就是一个可以被证明的定理，但考虑到 $F(n)$ 和 $G(n)$ 的任意性，我们仅把它作为一个经验公理。而如果公理1不成立，那么也就没有讨论 $P vs. NP$ 问题的必要了。

2 一个悖论和它的解决

    现在进入本文的核心部分。设 $h_1(n), h_2(n), \cdots, h_k(n)$ 为任意 $k(\leq n)$ 个关于 $n$ 的多项式函数，且 $H(n)=h_1(n)+h_2(n)+\cdots+h_k(n)$ 。请问 $H(n)$ 是关于 $n$ 的多项式函数还是指数函数？对于大多数学者来说，根据经验， $H(n)$ 总是一个多项式函数。但是，如果我们接受下面的命题1，那么就可以得到相互矛盾的两个结论（即一个悖论）。不失一般性，在本文中，我们假设 $n$ 总是偶数。

   命题 1 设 $h_1(n), h_2(n), \cdots, h_k(n)$ 为任意 $k(\leq n)$ 个关于 $n$ 的多项式函数，且 $H(n)=h_1(n)+h_2(n)+\cdots+h_k(n)$ ，则 $H(n)$ 总是一个关于 $n$ 的多项式函数。

   在接受命题1的条件下，我们可以构造出两个相互矛盾的结论，即引理3与引理4。

   设 $F(n)$ 和 $G(n)$ 如公理1中所定义。定义集合 $A=\{f(n)|$ 存在一个关于 $n$ 的多项式函数，不妨记为 $F(n)$ ，使得对于任意的 $n$ ，总有 $f(n)\leq F(n)$ $\}$ ，定义集合 $B=\{f(n)|$ 存在一个关于 $n$ 的指数函数，不妨记为 $G(n)$ ，使得对于任意的 $n$ ，总有 $f(n)\geq G(n)$ $\}$ 。

   引理 3 不存在函数 $f(n)$ ，使得 $f(n)\in A$ 且 $f(n)\in B$ 。

   证明：反证法。如果存在函数 $f'(n)$ 满足 $f'(n)\in A$ 且 $f'(n)\in B$ ，那么根据集合 $A$ 和集合 $B$ 的定义，必然存在多项式函数 $F'(n)$ 和 $G'(n)$ ，使得 $G'(n)\leq f'(n)\leq F'(n)$ 。也就是 $\frac{F'(n)}{G'(n)}\geq 1$ 对于任意的 $n$ 总成立，从而 $\lim\limits_{n\rightarrow \infty}\frac{F'(n)}{G'(n)}\geq 1$ ，与公理1矛盾。引理得证。

    引理 4 令 $\bar{f}(n)=C_n^{n/2}$ ，则 $\bar{f}(n)\in A$ 且 $\bar{f}(n)\in B$ 。

    证明：根据引理1，易知 $\bar{f}(n)\in B$ 。下面我们将通过 $\frac{n}{2}-1$ 步来证明 $\bar{f}(n)\in A$ 。根据集合 $A$ 的定义，只需证明存在关于 $n$ 的多项式函数 $F_0(n)$ ，使得 $C_n^{n/2}\leq F_0(n)$ 对于任意的 $n$ 成立即可。第一步，根据引理2，我们有 $C_n^{n/2}=C_{n/2-1}^{n/2-1}+C_{n/2}^{n/2-1}+\cdots+C_{n-1}^{n/2-1}$ ；注意到 $C_{n/2-1}^{n/2-1}

   现在，在接受命题1的条件下，我们构造出了相互矛盾的两个引理（引理3、引理4），所以，我们只能接受下面的命题了。

   命题 2 存在某 $k(\leq n)$ 个关于 $n$ 的多项式 $h_1(n)$, $h_2(n)$, $\cdots$, $h_k(n)$ ，使得 $H(n)$ 为关于 $n$ 的指数函数，其中 $H(n)=h_1(n)+h_2(n)+\cdots+h_k(n)$ 。

   注意到 $H(n)\leq k\max\limits_{1\leq j\leq k}\{h_j(n)\}\leq n\max\limits_{1\leq j\leq k}\{h_j(n)\}$ 且 $\max\limits_{1\leq j\leq k}\{h_j(n)\}$ 是一个关于 $n$ 的多项式函数，而一个关于 $n$ 的多项式函数乘以 $n$ 还是一个多项式函数，有的学者基于此断定 $H(n)$ 总是多项式的。然而，如果我们接受

“一个关于 $n$ 的多项式函数乘以 $n$ 总是一个多项式函数”这个命题，那么根据类似的分析也可以得出一个悖论。所以，这样的反驳是不合适的。

   但是，我们怎么来理解这个命题呢？在人们的生活中有没有类似的体验？有！设想您在一个陌生的地方旅行，突然间，您发现自己“掉向”（即分辨不清东西南北）了。令 $\epsilon$ 表示最小的时间单位。根据我们的经验，如果在时刻 $t$ 没有“掉向”，那么在时刻 $t+\epsilon$ 我们也没有“掉向”。但是，我们必须承认存在时刻 $t^*$ ，在时刻 $t^*$ 时您没有“掉向”，但是在时刻 $t^*+\epsilon$ 您“掉向”了，否则您怎么会“掉向”呢？虽然我们需要承认时刻 $t^*$ 的存在性，但是却没有人能够确切指出它。类似地，在命题2中，我们虽然需要承认 $h_1(n)$, $h_2(n)$, $\cdots$, $h_k(n)$ 的存在性，但是却也无法给出其具体表达式。基于此，我们认为命题2不仅是一个数学问题，更是人类认知的问题，即事物在发展变化时，刚开始只是“量变”，但会发展成“质变”，我们需要承认这种变化，但是却无法指出“最初“发生“质变”的那一瞬间。

3 $P\neq NP$ 的证明

   接受命题2后，我们很容易就可以证明 $P\neq NP$ 了。实际上我们只需构造出一个问题 $\Pi$ ，使得 $\Pi\in NP$ 且 $\Pi\notin P$ 。

   首先，根据命题2，我们知道存在 $k(\leq n)$ 个多项式函数，不妨设为 $h^*_1(n), h^*_2(n), \cdots,h^*_k(n)$ ，使得 $H^*(n)$ 为关于 $n$ 的指数函数，其中 $H^*(n)=h^*_1(n)+h^*_2(n)+\cdots+h^*_k(n)$ 。

   然后，我们知道一个判定问题的返回值是”是“或”否“。令 $\pi_i$ （ $i=1, 2, \cdots, k$ ）表示一个输入为 $I_i$ 的判定问题，其中它的输入长度 $|I_i|=n$ ，且它在最坏情形下的运行时间为 $h^*_i(n)$ 。定义问题 $\Pi$ ：给定任意输入 $I_1, I_2,\cdots,I_k$ ，在 $\pi_1,\pi_2,\cdots\pi_k$ 的返回值中是否有一个”是“。注意，问题 $\Pi$ 的输入长度为 $|I_1|+|I_2|+\cdots+|I_k|\leq kn\leq n^2$ 。

  定理  $P\neq NP$ 。

   证明：只需证明 $\Pi\in NP$ 且即可。注意到 $I_1, I_2,\cdots,I_k$ 是相互独立的，任意的确定性图灵机在最坏情形下都需要检查全部的返回结果，所以需要的运行时间为 $h^*_1(n)+h^*_2(n)+\cdots+h^*_k(n)$ $=H^*(n)$ ，为关于 $n$ 的指数函数，从而。

   另一方面，对于非确定性图灵机而言，它只需检查 $k$ 个返回结果中的一个就可以了，需要的运行时间显然为关于 $n$ 的多项式函数，于是 $\Pi\in NP$ 。定理得证。

4 结论

   本文从多项式函数的加法运算这一角度证明了 $P\neq NP$ 。并指出这不仅是一个数学角度，更是一个人类基本认知的角度。

    最后，衷心感谢您对本文的关注与意见！！！祝您身体健康，工作顺利，阖家欢乐！！！