汉语是联合国官方正式使用的 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, 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年（十四年）的耐心等待。

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

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

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

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

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

感谢您的指教！

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

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