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

博文

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

已有 2827 次阅读 2015-8-19 15:54 |系统分类:论文交流| 复杂性, 算法, 图灵机, NPC

 

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$ 。并指出这不仅是一个数学角度,更是一个人类基本认知的角度。

 

 

 

 

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

 

 

 

 



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

上一篇:P vs. NP 问题——一个有趣的视角
下一篇:P≠NP——基于多项式函数的加法运算的视角

1 姜咏江

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

数据加载中...

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

GMT+8, 2020-10-30 06:06

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部