wingss的个人博客分享 http://blog.sciencenet.cn/u/wingss

博文

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

已有 2918 次阅读 2016-11-22 16:49 |系统分类:科研笔记

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部分思路完全相同,而且非常简单。这里就不再重复了。



http://blog.sciencenet.cn/blog-2446134-1016165.html

上一篇:P≠NP——基于认知的视角

0

该博文允许注册用户评论 请点击登录 评论 (7 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-10-30 07:32

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部