博文

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

已有 1995 次阅读 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年，作为公派自费生，张益唐师从***在美国普渡大学攻读博士学位。