P≠NP——基于多项式函数加法运算的视角

（xbdxzwm@163.com）

   P vs. NP问题在科学网一直颇受观注，许多学者发表了自己的看法，甚至给出了它的回答。而我自己对这个问题的认识也在不断清晰化，在这之前，我发表了两篇博客，阐述了自己的观点。为了更加清晰简洁的把我的观点阐述清楚，力争使大家在20分钟之内即可明白我的观点，在此发表第三篇博客，与各位前辈同行共同交流。

   简言之，我认为这个问题是一个观念性问题，而并不是一个技术性问题。重点在于理清我们的一些基本观念，而不是动脑筋设计一个算法。

   于是，工作的重点就是要把这个“观念性问题”，用简单的数学语言呈现出来，让大家看到、认识到：“P vs. NP问题的根源在于过分强调多项式函数与指数函数的不同是真实的、彻底的、绝对的，而实际上，多项式函数与指数函数是密切相关的，不能彻底划分清楚。”进一步说，如果我们仍然把多项式函数和指数函数当作两个概念，那么一定会存在文中命题2这样有点匪夷所思的命题，这时就有了P不等于NP（当然了，这对科学的发展似乎意义并不大）。而如果莫视命题2的存在，认为命题1绝对正确，倒是真的可以证明P等于NP（不过这个结论不正确）。（这段话整理自博客的评论）  

摘  要

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

    我的观点的核心是下面的一个悖论。（本文中的函数都是指关于 $n$ 的函数，所以“关于 $n$ 的多项式函数”简称为“多项式函数”。）

1 悖论    

   命题 1 $n$ 个关于 $n$ 的多项式的和，总是一个关于 $n$ 的多项式函数。    

   即，设 $h_1(n), h_2(n),\cdots, h_n(n)$ 为任意 $n$ 个多项式函数，且 $H(n)=h_1(n)+h_2(n)+\cdots+h_n(n)$ ，则 $H(n)$ 一定是一个多项式函数。    

   这个命题看似一定正确，但是如何证明？有的学者可能认为， $H(n)=h_1(n)+h_2(n)+\cdots+h_n(n) \leq n\max \{h_1(n),h_2(n),\cdots, h_n(n)\}$ 且 $\max\{h_1(n),h_2(n),\cdots,h_n(n)\}$ 是一个多项式，因为“一个关于 $n$ 的多项式函数乘以 $n$ ，总得到一个多项式函数”，所以， $H(n)$ 一定是多项式函数。  

   这个证明正确吗？实际上，上面的证明用到了“一个关于 $n$ 的多项式函数乘以 $n$ ，总得到一个多项式函数”，而它事实上已经承认了命题1的正确性，所以，不可以这样证明。    

   所以，现在命题1仅仅就是一个命题，而不是一个定理。实际上，我们如果认为命题1一定成立，那么可以证明 $n^n$ 是一个多项式，即得到一个悖论（因为，显然 $n^n$ 并不是一个多项式）。

  定理 1 若命题1成立，则 $n^n$ 是一个多项式。

   证明：如下图所示，因为 $n^n=n^{n-1}+n^{n-1}+\cdots+n^{n-1}$ ，根据命题1，只需证明 $n^{n-1}$ 是一个多项式即可；而 $n^{n-1}=n^{n-2}+n^{n-2}+\cdots+n^{n-2}$ ，所以，根据命题1，只需证明 $n^{n-2}$ 是多项式即可；而 $n^{n-2}=n^{n-3}+n^{n-3}+\cdots+n^{n-3}$ …………只需证明 $n^2$ 是多项式即可；而 $n^2=n+n+\cdots+n$ ，根据命题1，只需证明 $n$ 是多项式即可，而 $n$ 是多项式是显然成立的。证毕。

   现在，我们得到了命题1一定成立的悖论了！于是，我们需要接受这样的现状了： $n$ 个多项式的和有时是多项式（例如 $n$ 个 $n$ 相加，还是多项式），有的时候并不是。即有下面的命题。    

   命题 2 存在某 $n$ 个关于 $n$ 的多项式的和，不是关于 $n$ 的多项式函数。

   关于这个命题的一些思考，可以参考我的第2篇博客（http://blog.sciencenet.cn/home.php?mod=space&uid=2446134&do=blog&id=914263），这里就不再重述了。如果我们承认了命题2，那么是很容易证明P≠NP的。  

2 $P\neq NP$ 的证明    

      实际上，证明思路与第2篇博客http://blog.sciencenet.cn/home.php?mod=space&uid=2446134&do=blog&id=914263的第3部分思路完全相同，而且非常简单。这里就不再重复了。