[往日（19）, P vs NP]：从互容、排序、矩阵乘法、定性推理，到 P vs NP

核心：

   在1993年底完成“P vs NP”思考之前，

   我已经思考过了“互容、排序、矩阵乘法”等多个相对较小的问题；

   以及1988年春天的一个“吓死人”的大问题。

   物极必反，

   从2003年开始的“电磁学的实验再检验（经典电磁学实验当代再检验）”思考，本来是更更“吓死人”的。

   但是，由于《中国大百科全书》里“库仑定律/Coulomb's law”等词条，

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

   不仅不“更更‘吓死人’”，反而成了《物理学》里“最主流”的有力标志！

    以下回忆，时间等不一定很准确，但应该差不太多。

一、互容 mutual capacitance

   1989年春季，开始考虑互容。就是《电路》中互感的对偶关系。秋天就基本上完成了所有的思考。我印象是1989年圣诞节前收到的《科学通报》“修改后录用”通知。当然，我不过圣诞节，我不信耶稣。

   在《科学通报》的痕迹：Accepted: May 28, 1990  Published: Jun 28, 1990。这个时间，应该是修改后的正式录用时间。

   1990年6月“互容的定义和模型——互感的对偶化”刊登在《科学通报》。

doi:  10.1360/csb1990-35-12-960

https://www.sciengine.com/CSB/doi/10.1360/csb1990-35-12-960

https://dds.sciengine.com/cfs/files/pdfs/view/0023-074X/QAGkJw4kRrudseW88-mark.pdf

   1992年在《IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications》刊出。

   2006年，在“Inductor winding capacitance cancellation using mutual capacitance concept for noise reduction application”一文里，三位 IEEE Fellows （含“美国工程院院士，National Academy of Engineering，Member”Fred C. Lee 李泽元老师）将“互容 mutual capacitance”概念记在我的名下。

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

   在大约1993年，俄罗斯 Taganrog State University of Radioengineering 的校长 V. G. Zaharevich （Vladislav Georgievich Zakharevich, Владислав Георгиевич Захаревич, 1946-10-12 ~ 2013-11-16）替他们学校的 S. N. Basan 教授、V. D. Mahinya 博士争取该概念的优先权。

   多年后，我觉得不要再争吵了：

   大明星费曼（Richard Phillips Feynman）在 1961-09 ~ 1963-05 的《费曼物理学讲义 The Feynman Lectures on Physics》里第二卷“22, AC Circuits”，早就定义了“mutual capacitance 互容”：

https://www.feynmanlectures.caltech.edu/II_22.html

Fig. 22-27.Equivalent circuit of mutual capacitance.

https://www.feynmanlectures.caltech.edu/II_22.html  

https://www.feynmanlectures.caltech.edu/img/FLP_II/f22-27/f22-27_tc_big.svgz

   不过，费曼似乎不是最早的。

   印象似乎在1940年代，就有学者定义了互容这个概念。

   我在“互容 mutual capacitance”上的具体贡献：

   （1）从定义，到可实现的物理模型，互容的完整电路性质，所有工作都完成了。

   （2）预言了可能做出新型的集成电路。

   上面“可实现的物理模型、完整电路性质、新型的集成电路”是我独有的贡献。特别是“可实现的物理模型、新型的集成电路”别人似乎都没有。

   尤其是在“半电路、半电磁场”电路方面，

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

   我怀疑“费曼这是想气死麦克斯韦啊？”

   1958~1959，基尔比、诺伊斯等人已经研制出了集成电路。可能费曼老师没有关心这件事情，因为就连电子行业内部，此时对集成电路还争议不断，不少权威认为集成电路没有前途。

   我1989年考虑互容，除了理论意义之外，另一个主要原因就是用于制作集成电路。我的物理模型可以用于生产，而费曼老师的物理模型基本上不能用于生产。费曼老师互容模型的“互容”参数，实在太小了。

二、排序 sorting，以及矩阵乘法 Matrix multiplication

   在1989年夏天基本完成“互容 mutual capacitance”的核心工作后，我逐渐看到《科学通报》1989春天的“矩阵乘法的一个最佳算法”、夏天的“分级快速排序法研究”二文。当然还有后来1990年春天的“关于矩阵乘法的一个最佳算法”。于是，又开始学习和思考这两个问题。

   由于我已经学过硕士生课程《数据结构与算法》，所以知道这两个问题的重要性：

   （1）“排序 sorting”

   至少有两位图灵奖得主（A.M. Turing Award Laureate）花力气研究过该问题。

   Tony Hoare (Sir Charles Antony Richard Hoare, C. ANTONY ("TONY") R. HOARE) 在 1961 年提出了“Quicksort 快速排序”。迄今为止，这是综合性能最好的实用排序算法；至少是在其后的 40年里。

   2001年，Tim Peters 先生用 Python 写出了 Timsort。据报道，Timsort 是一个超过 Hoare “Quicksort 快速排序”的更好算法。

   另一位 Donald Knuth (Donald Ervin Knuth, DONALD ("DON") ERVIN KNUTH)，更是以《The Art of Computer Programming 计算机程序设计艺术》闻名天下。“Sorting and searching”是该书的第三卷。

   （2）“矩阵乘法 Matrix multiplication”

   1968年，“great scientist 大科学家”Volker Strassen 提出了矩阵乘法的“Strassen Algorithm, Strassen算法”，以乘法的时间复杂性 N^log₂⁷ = N^2.807 突破了定义要求的 N³，轰动了学术界。

   将 Volker Strassen 称为“great scientist 大科学家”, 是 MacTutor 里的说法。不是我个人的看法。

https://mathshistory.st-andrews.ac.uk/Biographies/Strassen/

三、从排序、矩阵乘法到P对NP“P vs NP, P versus NP”答案的相对性

P vs NP - Clay Mathematics Institute

https://www.claymath.org/millennium/p-vs-np/

3.1  排序、矩阵乘法：算法复杂性的相对性

   作为爱因斯坦的粉丝，我本能地用“四维时空不变量”的思路去看待算法问题，本能地提出了“时间空间乘积（时空积）”的猜想。

   并且，在“矩阵乘法 Matrix multiplication”里，这个时空积就是 N³logN。

   显然，1968年“great scientist 大科学家”Volker Strassen 的 Strassen算法，不能排除是一个“近似算法”的可能性。浙江大学陈道琦、谢友才、应文隆三位老师的“关于矩阵乘法的一个最佳算法”起到了关键的启发作用！

   当将“时空积猜想”用于排序时，出现了两个不同的结果：采用“比较”运算的时间复杂性下限是 NlogN，而采用“乘法、除法”运算的时间复杂性下限是 N。

   正是为解决这个苦恼，才找到 Chaitin 定理，以及大数学家柯尔莫哥洛夫和索洛莫诺夫（Raymond J. Solomonoff, 1926-07-25 ~ 2009-12-07）的相关论文。以至于后来动辄就“宣布优先权”，这也是从柯尔莫哥洛夫 Kolmogorov、索洛莫诺夫 Solomonoff 两位老师合作的一篇英文短文里学来的。

   此时，常去南开大学数学研究所（现名“陈省身数学研究所”）图书馆查阅资料。这是华北地区最大的数学类图书馆。后来我去北京查资料时，一位图书馆的老师告诉我：“你为什么来北京查资料？南开大学数学研究所图书馆是华北地区最大的数学类图书馆。”

   在南开大学数学研究所图书馆，我两次近距离目睹数学大师陈省身先生（Shiing-shen Chern, 1911-01-26 ~ 2004-12-03）的风采。

   所以，才有了：

   （1）《中国科学报》2013-12-23，第6版 博客：数学大师陈省身的南开居所

   https://news.sciencenet.cn/dz/dznews_photo.aspx?id=19177

   https://news.sciencenet.cn/sbhtmlnews/2013/12/281620.shtm

   （2）《中国科学报》2014-12-05，第8版 博客：走廊：追忆陈省身先生的足迹

   https://news.sciencenet.cn/dz/dznews_photo.aspx?id=21931

   https://news.nankai.edu.cn/mtnk/system/2014/12/05/000211977.shtml

   更使我惊奇的是：

   我真正用到的那些数学专著和教材，在我们天津大学图书馆里一本都不缺！数年后我在我校图书馆里看到它们时，惊呆了！还有那本彩色的航拍地图册，一本厚厚的硬纸彩色印刷的大书！！

3.2  孔子、老子

   孔子老师《论语·卫灵公篇》：“工欲善其事，必先利其器。”

   老子老师《道德经·第五十四章》：“故以身观身，以家观家，以乡观乡，以邦观邦，以天下观天下。吾何以知天下之然哉？以此。”

   还有后来作为“哥德尔第一不完全性定理”具体化的 1966~1974年的 Chaitin 定理：“Unfortunately, any formal system in which it is possible to determine each string of complexity less than n has either one grave problem or another. Either it has few bits of axioms and needs incredibly long proofs, or it has short proofs but an incredibly great number of bits of axioms. 不幸的是，任何一个可以确定每个复杂度小于 n 的字符串的形式系统都有一个或另一个严重的问题。要么它有很少的公理，需要非常长的证明，要么它有很短的证明，但有非常多的公理。”

3.3  “P对NP”答案的相对性

   一点也不必担心了。

   像爱因斯坦一样，从哲学出发来思考科技的基础问题吧！

   这需要一定的阅读。阅读范围太窄，不一定就真正可以做到“深入”。

   “不谋万世者，不足谋一时；不谋全局者，不足谋一域。”

   上面的经历，证明了

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

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

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

   实际上，1988年春天，还有一个“比 P vs NP 大得多的核心思路”的发现。之所以 1992年下半年才真正关注“P vs NP”，就是因为那个“大得多的核心思路”一直在耗费我的精力。1995年夏天将该“比 P vs NP 大得多的核心思路”转化为数学公式，2008年11月在南开大学承办的教育部《科学素质教育课程骨干教师高级研修班》的大会发言里，向老师们汇报了这个思考：

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

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

   两个可能十分严重的后果：

   国际单位制(SI)中“安培”的定义，由于缺少关于电流方向的说明，需要修改。

   另一个，就是这个“吓死人”的思考。

2020-10-04，[优先权？] 中国人首先提出 SI 基本单位“安培”新定义？

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

附录（1）：

   在近几年“电磁学的实验再检验”、“自然运算”的思考方面，还是按照偶像爱因斯坦从哲学出发的思路。

   正是从哲学出发，才在“P vs NP”上避免了“张益唐也曾牺牲在雅可比猜想上”的悲剧。

   张益唐也曾牺牲在雅可比猜想上，并且比较惨重。他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 页

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

   解决一个问题的途径，可能有多种。就像《概率论》里的“正态分布 normal distribution”，历史上至少有4种不同的推导思路。

   “第二类数域”的提出，人工智能领域里的“定性推理 Qualitative Reasoning”，是重要的起因之一：

杨正瓴. 定性推理经典方法的数学结构分析[EB/OL]. 北京：中国科技论文在线 [2005-04-28].

http://www.paper.edu.cn/releasepaper/content/200504-178.

附录（2）：

   解决一个大的数学问题，往往需要多年的时间。丘成桐老师给出的精力：“完成一个好题目，也就是差不多完成三个小题目的时间和精力。”

https://blog.sciencenet.cn/blog-3377-1251601.html

   从怀尔斯（Andrew Wiles）证明“费马大猜想”、佩雷尔曼（Grigoriy Perelman）证明庞加莱猜想（Poincaré conjecture）看，时间大约为8年。

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

   从我1988年秋天听说“P vs NP”，到 1993年底完成全部思考，时间为5年。如果把学习《古今数学思想》、《中国大百科全书·数学》、《从一到无穷大》等算上，也是8年左右的时间。后面这些，是无意识的提前的准备。

附录（3）：

   比“吓死人”还要更“吓死人”，更更“吓死人”！

   就是“电磁学的实验再检验”。

   由于有了《中国大百科全书》几个词条，

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

   如“库仑定律/Coulomb's law”里的“电磁场理论的麦克斯韦方程组是在一些电磁学实验定律的基础上建立起来的，这些实验定律的精度和适用范围都难以言明”，“因此，电力平方反比律的精确验证实验还将长盛不衰地做下去。”

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

   本来更更“吓死人”的思考，反而成了“最主流”的有力标志！真是物极必反啊！

参考资料：

[1] 杨正瓴. 互容的定义和模型——互感的对偶化[J]. 科学通报, 1990, 35(12):  960 - 960.   Published: Jun 28, 1990   

doi:  10.1360/csb1990-35-12-960

https://www.sciengine.com/CSB/doi/10.1360/csb1990-35-12-960

https://dds.sciengine.com/cfs/files/pdfs/view/0023-074X/QAGkJw4kRrudseW88-mark.pdf

file:///C:/Users/Dell/Downloads/QAGkJw4kRrudseW88-mark.pdf

[2] 杨正瓴. 关于“互容”概念的意义. 南京: [J]电工教学, 1995, 17(4): 35-39.

http://qikan.cqvip.com/Qikan/Article/Detail?id=2000725&from=Qikan_Search_Index

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

https://d.wanfangdata.com.cn/periodical/QK199500046092

[3] 杨正瓴. 一种新型集成电路概念——串音计算. 北京: [N]中国科学报, 2019-08-15, 第7版 信息技术.

http://paper.sciencenet.cn/dz/dzzz_1.aspx?dzsbqkid=33013

http://paper.sciencenet.cn/dz/upload/2019/8/201981505629684.pdf

https://news.sciencenet.cn/sbhtmlnews/2019/8/348727.shtm

[4] The Feynman Lectures on Physics, 22, AC Circuits

https://www.feynmanlectures.caltech.edu/II_22.html

Fig. 22-27.Equivalent circuit of mutual capacitance.

https://www.feynmanlectures.caltech.edu/II_22.html

[5] 蒋昌俊, 吴哲辉. 矩阵乘法的一个最佳算法[J]. 科学通报, 1989, 34(4):  251 - 254.   Published: Feb 28, 1989   

doi:  0.1360/csb1989-34-4-251

https://www.sciengine.com/CSB/doi/10.1360/csb1989-34-4-251

file:///C:/Users/Dell/Downloads/tat5b8SrHzkfkAd2B-mark.pdf

[6] 杨宪泽. 分级快速排序法研究[J]. 科学通报, 1989, 34(11): 871 - 873.  Published: Jun 15, 1989   

doi:  10.1360/csb1989-34-11-871

https://www.sciengine.com/CSB/doi/10.1360/csb1989-34-11-871

file:///C:/Users/Dell/Downloads/TgqJvB8aEhj4xQy5g-mark.pdf

[7] 陈道琦, 谢友才, 应文隆. 关于矩阵乘法的一个最佳算法[J]. 科学通报, 1990, 35(3):  161 - 162.   Published: Feb 15, 1990   

doi:  10.1360/csb1990-35-3-161

https://www.sciengine.com/CSB/doi/10.1360/csb1990-35-3-161

file:///C:/Users/Dell/Downloads/Ytbrh3pQdahPHdYbg-mark.pdf

[8] C. ANTONY ("TONY") R. HOARE, United Kingdom – 1980, A.M. Turing Award Laureate

https://amturing.acm.org/award_winners/hoare_4622167.cfm

https://amturing.acm.org/alphabetical.cfm

https://amturing.acm.org/byyear.cfm

[9] DONALD ("DON") ERVIN KNUTH, United States – 1974, A.M. Turing Award Laureate

https://amturing.acm.org/award_winners/knuth_1013846.cfm

https://amturing.acm.org/alphabetical.cfm

https://amturing.acm.org/byyear.cfm

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

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

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

https://skerritt.blog/timsort/

[12] BAELDUNG, 2024-03-18, Quicksort vs. Timsort

https://www.baeldung.com/cs/quicksort-vs-timsort

[13] BAELDUNG, 2024-03-18, Matrix Multiplication Algorithm Time Complexity

https://www.baeldung.com/cs/matrix-multiplication-algorithms

[14] Volker Strassen, MacTutor History of Mathematics Archive

https://mathshistory.st-andrews.ac.uk/Biographies/Strassen/

[15] Shiing-shen Chern, MacTutor History of Mathematics Archive

https://mathshistory.st-andrews.ac.uk/Biographies/Chern/

[16] 陈省身数学研究，南开大学，天津，中国

Chern Institute of Mathematics, Nankai University, Tianjin,China. 300071

http://www.nim.nankai.edu.cn/6692/list.htm

[17] 陈省身数学研究所图书馆

http://www.cim.nankai.edu.cn/2018/0130/c6697a89769/page.htm

   陈省身数学研究所图书馆成立于1985年，由国际数学大师陈省身先生亲自领导创建。原址坐落于香港慈善家邵逸夫先生捐款300万港币与政府出资70万人民币共同兴建的逸夫馆，2005年数学图书馆迁入国家投资1.29亿元建设的“省身楼”中，位于A区3-6层，总建筑面积近4000平方米。

[18] 汤涛（中国科学院院士）. 张益唐和北大数学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

相关链接：

[1] 2023-07-28，[小资料] 将“互容 mutual capacitance”概念记在我名下的三位 IEEE Fellows 与院士

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

[2] 2021-05-02，往日（5）：1993年 IEEE 的一则 Erratum 勘误（互容 mutual capacitance）

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

[3] 2019-07-10，电路概念《互容》汇报后记

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

[4] 2023-08-05 21:57，[推测] “半电路、半电磁场”电路的价值，大于“晶体管+集成电路”

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

[5] 2022-07-07，[小资料] 真数学原创需要多长时间（怀尔斯、佩雷尔曼）

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

[6] 2020-10-02，[严肃内容] 2019年 SI 的新“安培定义”，是对我2012年第二方案的细化

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

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

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

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

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

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

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

[10] 2024-04-13，[数学文化，P vs NP] 正态分布的四种推导

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

[11] 2023-07-14，“电磁学的实验再检验”：经典电磁学实验当代再检验的起因、意义要点

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

[12] 2023-10-26，[最主流，实体的物理实验波形] “费曼电容器充电”的电压波形观察

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

[13] 2024-01-05，[笔记，请教，原创] “自然运算”信息设备的一般理论模式

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

[14] 2023-12-27，[笔记，请教，原创] “自然运算”有什么创新？

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

[15] 2023-08-04，[回忆] 老家南堤下村与对祖先们的些许记忆

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

[16] 2022-06-03，[回忆] 我们的科技类代表性观点（或论文）（1）：“常规”研究的部分

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

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

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

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

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

[19] 2024-05-07，[怀旧，回顾，展望] 与非门 NAND Gate, 或非门 NOR Gate

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

[20] 2023-08-11，[怀旧，回顾，展望] 二极管与非门，场效应晶体管

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

[21] 2023-03-04，往日（18）：SI “词头 prefixes”与科技话语权

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

[22] 2019-02-28，往日（1）：小样本数理统计学与“压缩感知 Compressed sensing”

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

[23] 2019-07-02，记忆：南开大学2008年《科学素质教育课程骨干教师高级研修班》

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

感谢您的指教！

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

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