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

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

Not to discriminate against Chinese, please!

[请教，P vs NP] 从前（4）：从“排序 sorting”到“P对NP, P vs NP”

狄利克雷（Johann Peter Gustav Lejeune Dirichlet）：

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

Replacing blind calculations by clear ideas.”

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

https://cdn.quotesgram.com/img/48/48/1189461077-Donald-Knuth.jpg

https://quotesgram.com/donald-knuth-quotes/

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

核心提示：

是什么性质，将N!（指数界）个数候选解的排序问题，

简化为 O(NlogN) 的计算量？

一、1993年暑假，“P对NP, P vs NP”的形转换与幂集公理

   真正下决心思考“P对NP, P vs NP”是1993年暑假。很快发现了“形转换”（弱证明），幂集公理（直接证明），以及 NPI 和连续统假设的关系。

   1993年底之前，基本上完全解决了“P对NP, P vs NP”。

   牛顿对此很不以为然：还差一个“概率化”方法吧？

   果然，

   2010年前后，我抽空又想了想。还真有“概率化”的弱证明。

   至此，“P对NP, P vs NP”的“1+3”个方法都齐全了。

   接着，牛顿又愤愤不平地说：

   “我的科学、哲学水平，人们不好乱说了。我的侦探水平、炒股水平、官爵，也都不低啊！”“就这样，还有人说我‘不懂艺术’！”。

二、“排序 sorting”、矩阵乘法

   1993年之前，我还思考过“排序 sorting”算法，以及矩阵乘法：

   （1）“排序 sorting”的信息论下界 NlogN。但不用“比较”作为基本运算，对于许多情况（如，Ляпунов 稳定的系统行为采样得到的数据，包括其概率化推广的那些更复杂的系统行为），从理论上存在渐渐O(N)的排序算法。

   （2）矩阵乘法的最小信息量为 O(N³logN）。凡是比该信息量小的算法，以概率1是“近似”方法。通常以损失“有效数字位数”为代价。

三、“排序 sorting”与“P对NP, P vs NP”

   对于给定的N个数据，其全排列的数量为 N！。

   根据斯特林公式（Stirling's approximation），可知排序候选序列的数量，不低于指数界。

   核心，

   是什么性质，将N!（指数界）个数候选解的排序，简化为 O(NlogN) 的计算量？

   类似地，3SAT 是 NPC；但是，2SAT 是 P！

   “大多数指数时间算法只是穷举搜索法的变种, 而多项式时间算法通常只有在对问题的结构有了某些比较深入的了解之后才能给出。”不知道这句话出处的人，没有弄清楚“P对NP”，应该不算奇怪。

   这是解决“P对NP, P vs NP”的关键中间步骤之一。“排序 sorting”和“2SAT 是 P”，实现了“用清晰的思想代替盲目的计算 Replacing blind calculations by clear ideas.”Peter Gustav Lejeune Dirichlet, 1805-02-13 ~ 1859-05-05。

   费米的回答很清楚，他说，他觉得大题目、小题目都可以想，可以做，不过多半的时候应该做小题目。如果一个人专门做大题目的话，成功的可能性可能很小，而得精神病的可能很大。做了很多的小题目以后有一个好处，因为从各种不同的题目里头可以吸取不同的经验，那么，有一天他把这些经验积累在一起，常常可以解决一些本来不能解决的问题。

引用自：杨振宁. 我的治学经历与体会[J]. 高等教育研究, 1995, 16(5): 1-3,6.

https://www.cnki.com.cn/Article/CJFDTotal-HIGH199505002.htm

PS附言（1）：

   对“排序 sorting”和矩阵乘法的学习与思考，逐渐使我产生了“问题的体积”（最小时间-空间乘积）的猜想。您一定想到俺的偶像爱因斯坦的“四维时空”不变量了吧？是的！有相当直接的文化背景原因！！

   这个猜想，和理论计算机科学中的“相似性原理”（洪加威），柯尔莫哥洛夫（Андрей Николаевич Колмогоров, Andreï Nikolaïevitch Kolmogorov）、索洛莫诺夫（Raymond J. Solomonoff）的“算法复杂性”之间有某种类似性。

   这就是为什么后来我一直极力推荐 Chaitin 定理的原因。不仅仅是以为“工欲善其事，必先利其器”。毕竟知道“工欲善其事，必先利其器”人远远不止我一人啊！

图2  索洛莫诺夫 Raymond J. Solomonoff, 1926-07-25 ~ 2009-12-07

https://raysolomonoff.com/ray1.jpg

https://raysolomonoff.com/

https://people.idsia.ch/~juergen/ray.html

PS附言（2）：

   “宣布优先权。”也是从柯尔莫哥洛夫 Kolmogorov、索洛莫诺夫 Solomonoff 合作的一篇英文短文里学来的。我想应该没有记错。

   可惜现在一时没有找到该文。毕竟30年过去了，现在我仍然没有时间。

推荐阅读：

[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] 2023-06-26，桶排序/bucket sort/冯启龙，中国大百科全书，第三版网络版[DB/OL]

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

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

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

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

https://www-cs-faculty.stanford.edu/~knuth/taocp.html

[7] CSDN，2022-08-16，Tim排序（Tim Sort）

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

[8] 知乎，2023-10-20，Python 中有几种常见的排序算法？

https://www.zhihu.com/question/484216921/answer/3256989888?utm_id=0

[9] 知乎，2024-01-07，Timsort：最快排序算法

https://zhuanlan.zhihu.com/p/676457775

[10] Geeksforgeeks, 2024-04-05, Sorting Algorithms

https://www.geeksforgeeks.org/sorting-algorithms/

[11] 2002, Tim Peters’ original introduction to Timsort

https://bugs.python.org/file4451/timsort.txt?ref=skerritt.blog

[12] Autumn Skerritt, 2023-06-20, Timsort — the fastest sorting algorithm you’ve never heard of

https://skerritt.blog/timsort/

[13] The Zen of Python, by Tim Peters

http://www.openbookproject.net/books/bpp4awd/_static/ch10/zen.html

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

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

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

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

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

[16] Stirling formula. Encyclopedia of Mathematics.

https://encyclopediaofmath.org/wiki/Stirling_formula

[17] Weisstein, Eric W. "Stirling's Approximation." From MathWorld--A Wolfram Web Resource.

https://mathworld.wolfram.com/StirlingsApproximation.html

[18] Matrix multiplication. Encyclopedia of Mathematics.

https://encyclopediaofmath.org/wiki/Matrix_multiplication

[19] Weisstein, Eric W. "Matrix Multiplication." From MathWorld--A Wolfram Web Resource.

https://mathworld.wolfram.com/MatrixMultiplication.html  

[20] 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

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

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

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

DOI:  https://doi.org/10.1201/9780429493768

[23] 杨振宁. 我的治学经历与体会[J]. 高等教育研究, 1995, 16(5): 1-3,6.

https://www.cnki.com.cn/Article/CJFDTotal-HIGH199505002.htm

[24] 姚期智. 科学家与科学之路[N]. 中国科学报, 2012-04-30 B1 思想周刊.

https://news.sciencenet.cn/sbhtmlnews/2012/4/257446.shtm

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

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

相关链接：

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

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

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

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

[3] 2023-12-25，[原创有多难] 饺子汤 （关联"P对NP, P vs NP, P versus NP"的答案）

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

[4] 2023-07-10，[请教，讨论] P对NP（九）：请您看看，您还有哪些批评或疑问？

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

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

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

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

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

[7] 2023-06-29，[请教] P对NP（三）：“NP完全性, NP-completeness”之后

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

[8] 2023-07-04，[请教] P对NP（四）：相关要点小结（问答式）

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

[9] 2024-03-27，从前（3）：“多信使相对论”（狭义相对论）

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

[10] 2024-03-26，[娱乐，？？？] 从前（2）：“级数相对论”的接近清晰的物理图像

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

[11] 2021-06-24，从前（1）：名字上了《中国科学报》2021-06-24 第3版 信息技术

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

感谢您的指教！

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

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