求真分享 http://blog.sciencenet.cn/u/zlyang 求真务实

博文

[P vs NP,数学文化] “排序 sorting”的信息论下界与“P对NP, P vs NP”答案的相对性

已有 1079 次阅读 2024-4-12 22:27 |个人分类:科学 - 艺术 - 社会|系统分类:科研笔记

汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语!

Chinese is one of the six equally effective official languages of the United Nations.

Not to discriminate against Chinese, please!

                                       

[P vs NP,数学文化] “排序 sorting”的信息论下界与“P对NP, P vs NP”答案的相对性

                                       

狄利克雷(Johann Peter Gustav Lejeune Dirichlet):

用清晰的思想代替盲目的计算

Replacing blind calculations by clear ideas.

                               

Donald Ervin Knuth 33 image-1024x1024.jpeg

高德纳 Donald Ervin Knuth, 1938-01-10 ~

https://j11g.com/wp-content/uploads/2020/12/image-1024x1024.jpeg

https://j11g.com/2020/12/30/podcast-donald-knuth-lectures-on-things-a-computer-scientist-rarely-talks-about/

https://news.sciencenet.cn/htmlnews/2010/3/229434.shtm

                           

核心提示:

是什么性质,将N!(指数界)个数候选解的排序问题,

简化为 O(NlogN的计算量?

       

一、如何突破“排序 sorting”的信息论下界O(NlogN)?

   “排序 sorting”的信息论下界 O(NlogN),是指用“数值比较大小”作为排序的主要“运算”进行排序的时间复杂性下界。在该“比较”运算下,O(NlogN)是不能突破的。

             

   但是,正如《中国大百科全书》词条“排序算法/sorting algorithm”:

   计数排序。算法将输入的数据值转化为键存储在额外开辟的数组空间中。

   算法时间复杂度为线性时间,但空间复杂度较高。

https://www.zgbk.com/ecph/words?SiteID=1&ID=95394&Type=bkzyb&SubID=81669

       

二、原因

   “比较”运算只对两个数据进行“整体的粗略”判断,没有使用数据自身携带的更丰富有效信息。

   “将输入的数据值转化为键存储在额外开辟的数组空间中”,计数排序更细致地使用了数据中“各位数字”的丰富信息,自然可以仅用 O(N时间,即低于的信息论下界 O(NlogN的时间完成排序。

   从理论上讲,“计数排序”的适用范围可以进一步扩大。此系天机,无可奉告。

       

三、“排序 sorting”的信息论下界:再看“P对NP, P vs NP”答案的相对性

   采用“简单”的“比较”运算,排序时间 O(NlogN)

   采用“高级”的“数据值转化为键存储”运算,排序时间可达 O(N)

   采用的运算高级了,计算的时间就缩短了。

       

   核心原因:

   “对问题的结构有了某些比较深入的了解”,是提高排序速度(降低时间复杂性)的核心方法。计数排序更细致地使用了数据中“各位数字”的丰富信息。

       

   还是孔子老师、老子老师、Chaitin 老师等多人的

   “工欲善其事,必先利其器。”

   “磨刀不误砍柴工”。

   详见《[P vs NP,讨论,交作业] 郑波尽老师:P vs NP 的本质,及其研究方法》

https://blog.sciencenet.cn/blog-107667-1426579.html

       

   于是,

   从头开始下决心将“P对NP, P vs NP”答案的相对化。

   独立于“P vs NP”的他人研究观点,孔子老师、老子老师、Chaitin 老师等的思想,以及排序算法两种不同下界(突破信息论下界)的直接启发,都使我下决心将“P对NP, P vs NP”答案的相对化。

       

PS附言(1):

   《The Art of Computer Programming, Volume 3, Sorting and Searching, by Donald Knuth, 1973; 722 pages. ( Addison-Wesley, £9·30.)》的汉译本:(美) Donald E. Knuth著. 计算机程序设计艺术. 第3卷. 排序与查找[M].

   差不多看了2、3年。主要是为了学习和思考“排序”算法。

       

   阅读该书时,感觉该书自身已经成为了一种“艺术”,大开眼界!

       

PS附言(2):

   正是我“一定要从头开始”的决心,避免了“张益唐也曾牺牲在雅可比猜想上”的悲剧。

       

   张益唐也曾牺牲在雅可比猜想上,并且比较惨重。他90年代博士毕业前夕,宣称解决了雅可比猜想,并且有几个专家对他的证明很感兴趣。但是,不幸的是他的证明里的一个引理是其*****的一篇发表的成果,本以为是对的,但再排查时,查出*教授之前的结果是错的。你应该知道后果很严重吧?张益唐几年的主要心血付之东流了!!

引用自:汤涛(中国科学院院士). 张益唐和北大数学78级[J]. 数学文化, 2013, 4(2): 3-20.

https://www.global-sci.org/intro/article_detail/mc/11633.html

https://www.global-sci.org/intro/articles_list/mc/1412.html

第 13 页

       

   一定要尽力核对“原始文献”,决不轻易表态!

   重要基础问题的思考,尽可能从哲学开始,就像青年时期的爱因斯坦。

   尽力避免以他人的研究中间结果为基础:尽管牛顿自称站在巨人的肩膀上。

       

PS附言(3):

   “反思麦克斯韦经典电磁理论”,大约是2003年开始的。长期不敢公开表态。综合几方面的参考资料之后,终于在 2017-02-19 首次公开表态。经过大约14年(十四年)的耐心等待。

火花 2017-02-19 13点37 建议从100多年前的电磁学经典实验_抠图_.png

https://idea.cas.cn/viewdoc.action?docid=4681

                      

   2023-10-26 下午,亲自动手实验,否证了费曼的电容器充电的理论解释。

   2018-08-28 《科学网》博文“关于电磁场“场”概念的局限性、电荷能量的偶感”贴出去之后,传闻有严肃的科学家用实体实验证实了。

   当然,樊京老师(博士后,教授)“这个实验我做过,对电阻一点儿影响没有。”

樊京 2018-09-01 18点33 这个实验我做过,对电阻一点儿影响没有.png

https://blog.sciencenet.cn/blog-107667-1131501.html

[7]樊京  2018-9-1 18:33

   "假如能流真的是通过“场 Poynting vector”传播,屏蔽后的电阻发热应该会有所下降" 这个实验我做过,对电阻一点儿影响没有。当然有人认为场永远不可被屏蔽。导线跑哪里,场就钻到哪里。我只想问:导线是爸,场是儿子?还是场是爸,导线是儿子?哈哈

    回 正瓴 : 

   有些问题明显摆在那儿,可砖家们置之不理。倒是研究起147亿年前的事情特别带劲。欧姆定律是凝聚态物理研究的对象,应该受量子理论支配。坡印廷能流在低频下完全没有物理意义,因为它既可以对应波能量的平衡,也可以对应电阻耗能的平衡。如果有外星人给我们的天线上输送了一点儿暗能量,坡印廷能流完全可以把外星人也算进去。 

   2018-9-2 09:40 2 楼(回复 1 楼)

                                

推荐阅读:

[1] 郑波尽,2024-03-16 22:48,杨正瓴的PvsNP证明

https://blog.sciencenet.cn/blog-241229-1425614.html

                                                              

参考资料:

[1] 2023-06-26,排序算法/sorting algorithm/王建新,中国大百科全书,第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=95394&Type=bkzyb&SubID=81669

[2] 2023-06-27,堆排序/heapsort/冯启龙,中国大百科全书,第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=375929&Type=bkzyb&SubID=81669

[3] 2023-06-26,快速排序/quicksort/冯启龙,中国大百科全书,第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=94352&Type=bkzyb&SubID=81669

[4] 2022-01-20,算法分析/analysis of algorithms/朱滨海,中国大百科全书,第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=107182&Type=bkzyb&SubID=81664

[5] Donald Ervin Knuth. The Art of Computer Programming, Volume 3,Sorting and Searching, Second Edition [M]. Reading, Massachusetts: Addison-Wesley, 1998.

[6] 2022-01-20,排列/permutation/郭龙,中国大百科全书,第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=109858&Type=bkzyb&SubID=61846

[7] 2022-12-23,置换/permutation/牟晨琪,中国大百科全书,第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=296257&Type=bkzyb&SubID=81645

   集合S的n个不同元素的全排列的个数为n!.

[8] Michael R. Garey,David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. United States: W. H. Freeman & Co., Subs. of Scientific American, Inc. 41 Madison Avenue, 37th Fl. New York, NY, 1979-01.

https://dl.acm.org/doi/10.5555/578533

[9] (美)M.R.加里,D.S.约翰逊 著, 张立昂,沈泓,毕源章 译. 计算机和难解性:NP完全性理论导引[M]. 北京: 科学出版社,1987.

[10] Frank Harary. Graph Theory [M]. Boca Raton: CRC Press, 1969. 

https://www.taylorfrancis.com/books/mono/10.1201/9780429493768/graph-theory-frank-harary

[11] 科学网,新京报,苏椰,2010-03-14,图灵奖史上最年轻获奖者高德纳:把一件平常事做到人间极致

https://news.sciencenet.cn/htmlnews/2010/3/229434.shtm

[12] 汤涛(中国科学院院士). 张益唐和北大数学78级[J]. 数学文化, 2013, 4(2): 3-20.

https://www.global-sci.org/intro/article_detail/mc/11633.html

https://www.global-sci.org/intro/articles_list/mc/1412.html

[13] 澎湃新闻,2022-10-27,突然爆红的张益唐是谁?

https://www.thepaper.cn/newsDetail_forward_20461489

   1985年,作为公派自费生,张益唐师从***在美国普渡大学攻读博士学位。

   但是,他的证明里有一个引理是*****的研究,***的成果后来被发现是错的,导致张益唐的证明也付之东流。

[14] CSDN,2022-08-16,Tim排序(Tim Sort)

https://blog.csdn.net/linjing_zyq/article/details/126335154

[15] 中国科学院科学智慧火花,杨正瓴,2012-04-12 10:46,SI基本单位中安培定义的两种可能缺陷

https://idea.cas.cn/viewdoc.action?docid=4681

                       

相关链接:

[1] 2024-04-11,[请教,P vs NP] 从前(4):从“排序 sorting”到“P对NP, P vs NP”

https://blog.sciencenet.cn/blog-107667-1429261.html

[2] 2024-01-25,[优先权?] “P对NP”已经解决。 The P vs NP (P versus NP) has been solved

https://blog.sciencenet.cn/blog-107667-1419345.html

[3] 2023-12-02,[重复就是力量] “P对NP, P vs NP, P versus NP”问题的情况汇报

https://blog.sciencenet.cn/blog-107667-1412189.html

[4] 2023-12-25,[原创有多难] 饺子汤 (关联"P对NP, P vs NP, P versus NP"的答案)

https://blog.sciencenet.cn/blog-107667-1415335.html

[5] 2023-07-10,[请教,讨论] P对NP(九):请您看看,您还有哪些批评或疑问?

https://blog.sciencenet.cn/blog-107667-1394865.html

[6] 2024-03-23,[P vs NP,讨论,交作业] 郑波尽老师:P vs NP 的本质,及其研究方法

https://blog.sciencenet.cn/blog-107667-1426579.html

[7] 2013-09-18,矩阵乘法需要O(n^3)的时间,不能再减少

https://blog.sciencenet.cn/blog-107667-725846.html

[8] 2023-06-29,[请教] P对NP(三):“NP完全性, NP-completeness”之后

https://blog.sciencenet.cn/blog-107667-1393466.html

[9] 2023-07-04,[请教] P对NP(四):相关要点小结(问答式)

https://blog.sciencenet.cn/blog-107667-1394027.html

[10] 2018-08-28,关于电磁场“场”概念的局限性、电荷能量的偶感

https://blog.sciencenet.cn/blog-107667-1131501.html

                        

感谢您的指教!

感谢您指正以上任何错误!

感谢您提供更多的相关资料!



https://blog.sciencenet.cn/blog-107667-1429437.html

上一篇:[请教,P vs NP] 从前(4):从“排序 sorting”到“P对NP, P vs NP”
下一篇:[数学文化,P vs NP] 正态分布的四种推导
收藏 IP: 202.113.11.*| 热度|

18 马丽丹 池德龙 王从彦 刘跃 郑永军 刘进平 黄河宁 钟炳 高宏 宁利中 崔锦华 孙南屏 钱大鹏 孙颉 王成玉 杨学祥 李学宽 王涛

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

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

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

GMT+8, 2024-5-22 19:34

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部