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

博文

黎曼猜想成立下P=NP的简易证明

已有 9953 次阅读 2022-4-7 18:55 |系统分类:观点评述

由黎曼猜想成立的结论可知,对素数的了解最多可以达到1/2(最少也是>0),因此对一个具体的数学系统(如旅行商问题,它可以看成最终是由素数组成的)最多可以了解1/2的信息(最少也是>0)。同样地,对于任意情况下响应面拟合的平均命中率(搜索深一层top解的命中率)也是>0的,对于任意情况下启发式搜索的平均命中率(搜索当前层top解中通往最优解拟合路径的种子解的命中率)也是>0的。

 

由于响应面拟合和启发式搜索都可以发现同层次的top解,因此不作为命中率的评判准则。响应面可以看作深度优先搜索,启发式可以看作广度优先搜索,两者结合起来,可以看作一种深度启发式搜索,即先响应面,再启发式,再更深一层的响应面,再更深一层的启发式……。这种深度启发式搜索的层次是有限的,根据旅行商问题的定义最多是N层(N是城市数目),最多从top 1/N层搜索到top 1/N^N层。然而进阶的过程并非总是正好是1层1层的,不然旅行商问题变成一个有规则的系统,应当将旅行商问题看成是一个有一定随机性的系统,那么进阶的过程可能是跳跃性的,最多直接跳跃到top 1/N^N层,平均而言层数可能是logN层。另外由和它相关的黎曼猜想的证明过程可以看出,素数公式余项的最大阶数也可能是logN阶,这是由分形数论函数方程的推导过程得出的猜测,当然也可能是N阶,但是较不可能。两者放在一起比较,可以看出logN是较有可能的层数和阶数,当然这需要严格的证明。

 

响应面受插值路径和插值方法的限制,找到深一层次的局部更优解的概率可以估计为1/10×1/10=1/100,其中前一个1/10是插值路径的选择对命中率的衰减估计,后一个1/10是具体的插值方法对命中率的衰减估计,当然这需要严格的证明。启发式找到同层次解(即前一次响应面拟合带来的深一层次top解的同层解)的概率估计为1/10(这是启发式的天然性质决定的,当然这需要严格的证明),找到同层次的通往最优解(通过响应面插值拟合路径)的种子解的概率估计为1/10(当然这需要严格的证明),因此总概率可以估计为1/10×1/10=1/100。两者结合使用,发现同层次(深一层次top解)的通往最优解的种子解的概率是1/100×1/100=1/10000。以上是由黎曼猜想成立的结论推出的,即素数的随机性大约为1/2,确定性也大约为1/2,估计响应面和启发式的每一阶段命中率(有效性度量)的时候可以不失一般性地再放大为1/10。由前面的讨论,深度启发式搜索(响应面+启发式)一共需要往深层使用大约logN次(类似素数分布公式的余项可以达到logN阶),这样发现最优解的概率就是(1/10000)^logN,因此需要重复实验约N^14次(N→∞)才能保证找到一个最优解。显然,这不是普通个人计算机能够承受的计算量,而是超级计算机或量子计算机能够承受的计算量。而随机数发生器的随机性(普通伪随机函数或大气噪音半真随机函数)保证了每次实验相互之间都有一定的独立性,便于概率的累积。如果万一深度启发式搜索需要往深层使用N次(类似素数分布公式的余项最多可以达到N阶),重复实验可以采用量子计算机,得到指数级效率的提升(当然可行性有待进一步考证)。

 

重复实验不仅仅指重复一次完整的最优解的搜索任务,每次搜索任务内部也可以有许多的重复实验,这涉及到NP多项式算法的构造问题。大体来说,这是一个迭代求精的过程,一个形象的描述是“森保一”或“森林木保一”,每次迭代后得到的大量解又分散到各个top解群里在下一次迭代时再次做群体式响应面拟合,我们说这个概率算法对重新排序组合的过程是保真的。

 

一个显然的问题是如何启动。最初只有0个解,可以通过蚁群算法去掉信息素挥发部分剩下的启发式搜索(结合强化学习反馈算法)大量采样得到10000个解,再以这10000个解为初始种群用虫洞/飞鸟算法、蚁群/强化学习算法、遗传/模拟退火算法三合一作为群启发式算法迭代10000次得到100000000个解,再从这些解里重新排序得到最小的10000个解和其余更大的100000000个解,这里又用到了此概率算法对重新排序组合的过程是保真的性质。接下来可以用二阶插值算法求深一层次(第三层)top解了。如果对这个过程不放心,可以再在外层做一个群启发式算法迭代,得到10000亿个解,然后用三阶插值算法求深一层次(第四层)top解。每条插值路径大约产生52个深一层次候选解(不一定都是深一层次的,这个数量由特定的插值算法决定,可以适当增减),对于二阶插值算法,由于只有两个点,之间的距离只有1个,即1步距离,还需要扩展采样距离到1步半距离和半步距离才能获得52个候选解。对于三阶以上插值算法,由于有多个点,扩展采样距离可以减少直到不需要,就可以获得52个候选解。这里用到了5种距离:采样点之间的平均距离、最小距离、最大距离、最佳距离(路径总长为0)、单位距离(全部看作1)。然后对每一个群启发式算法分别迭代100次,一共300次,得到约10000个启发式解。对每一个插值路径都这么做(这里不仅包括经过每个第一层top解的插值路径,也包括经过后续每一层top解的插值路径,去掉重复的插值路径,插值路径的构造采用最邻近连线路径的原则,如果采用最邻近的10个点或100个点的分别连线路径的原则,会导致采样点增加到N的指数阶个,并且这里的重复实验会遵循概率累积效应,不需要额外采样这么多点也可以搜索到最优解),得到约10000亿个新的采样点,可以简单地看成在原先的每一层采样点数量都乘以一个10000,最新的层为10000,继续深度启发式搜索的迭代过程直到找到1个最优解(最小解)。

 

还有一个需要注意的问题是每层解的分割问题,一般地,深度启发式搜索的过程中会找到远优于当前层的top解,这是由旅行商问题的随机性决定的。如果把它们放到当前层中来供下一次插值计算,因为插值路径的畸变可能会得不到更优的解。因此每一层的最优解的差距都是有限的,这个有限值可以由公式:[(最长N条边-最短N条边)/logN]大致决定,超过此差距的采样点归类于下一层top解群(比当前深一层top解群更深的top解群)并不参与插值,直到下一次迭代的时候再做同样的取舍。由于有限值公式的估计可能过大,这样一次完整的最优解搜索可能不会用到logN层,假设为k层,这个时候应该按照公式:[(最大解-最小解)/logN]重新排序组合得到新的logN层top解群,然后从其中第k层起,依次重新做插值算法-启发式算法的迭代,直到找到新的最优解(最小值)或者没有找到为止。这里又用到了此概率算法对重新排序组合的过程是保真的性质。logN层的预定深度是个大概的估计,一般为logN±C层,C为一个小的正整数。


可以独立地重复此搜索最优解的迭代算法M次,M是一个不大的正整数(M<< N^14),比较每次的搜索结果是否一致。经过这样两轮的迭代过程,一定可以找到一个旅行商问题的最优解。对于N比较小的问题而言,这相当于穷举,对于N比较大的问题而言,就是一个比较经济的多项式寻优算法。P=NP得证。正式的证明需要用到几何、代数、数论、图论、概率论、信息论、数值计算等方面的知识,在这不展开叙述。




https://blog.sciencenet.cn/blog-2955758-1332926.html

上一篇:黎曼猜想的一个证明
收藏 IP: 60.177.34.*| 热度|

0

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

数据加载中...
扫一扫,分享此博文

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

GMT+8, 2024-7-1 00:28

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部