博文
[P vs NP，讨论，交作业] 郑波尽老师：P vs NP 的本质，及其研究方法
||
汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语！
Chinese is one of the six equally effective official languages of the United Nations.
Not to discriminate against Chinese, please!
[P vs NP，讨论，交作业] 郑波尽老师：P vs NP 的本质，及其研究方法
图1 孔子老师《论语·卫灵公篇》：“工欲善其事，必先利其器。”
https://www.chinasource.org/wp-content/uploads/2020/04/Confucius_Sculpture__Nanjing-2-scaled.jpg
图2 老子老师《道德经·第五十四章》：
“故以身观身，以家观家，以乡观乡，以邦观邦，以天下观天下。
吾何以知天下之然哉？以此。”
https://img.daoisms.org/allimg/161026/4-1610261GR5Q4.jpg
https://www.daoisms.com.cn/article/sort018/info-26112.html
不听老人言，吃亏在眼前。
狄利克雷（Johann Peter Gustav Lejeune Dirichlet）：
“用清晰的思想代替盲目的计算
Replacing blind calculations by clear ideas.”
一、起因
首先，感谢郑波尽老师 2024-03-16 22:48 的博文《杨正瓴的PvsNP证明》。
2024-03-18 15:00，郑老师给我留作业：
https://blog.sciencenet.cn/blog-241229-1425614.html
那么，请写一篇文章说明，P！=NP的本质是什么？为什么其他证明方法都注定不成功？
2024-3-18 15:003 楼（回复楼主）
二、预备：工欲善其事，必先利其器
孔子老师在《论语·卫灵公篇》里说：“工欲善其事，必先利其器。”
后人有：
“没有金钢钻，别揽瓷器活。”
“磨刀不误砍柴工”。
不仅如此，作为哥德尔第一不完全性定理的详细化，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的字符串的形式系统都有一个或另一个严重的问题。要么它有很少的公理，需要非常长的证明，要么它有很短的证明，但有非常多的公理。
这可以看做是对“工欲善其事，必先利其器。”的一个现代化的细致的解释。
对于可以解决的问题，采用不同的工具，同一问题的求解难度也会不同。所以，
《增广贤文·下集》里说：
“难者不会，会者不难。”
https://so.gushiwen.cn/mingju/juv_5caac2a5b648.aspx
【译文】 对于不擅长的人来说，事情显得困难；而对于擅长的人来说，则轻而易举。
【赏析】 这句话简洁明了地阐述了技能与难度的关系，启示我们，要通过学习和实践来提升自身能力，以应对生活中的各种挑战。
三、交作业（1）：P！=NP的本质是什么？
用通常的数字计算机求解问题时，有的问题类（P类）有快速的计算方法，另一些问题类（NPC）一直没有找到快速方法。
于是，P类是否是NP类的严格子集，即 P=NP？ 成为50多年的有争议的难题。
关于 “P vs NP”（P versus NP, P对NP）的实质，傻以为需要从“问题类”、“计算机模型”两者之间的关系才能说清楚。
一般而言，“P 包含在 NP 里”没有争议。关键是“P = NP？”或者“P 是 NP 的一个真子集？”，这是个有争议的问题，即著名的千禧年问题“P vs NP”。
由于 NDTM（NTM）可以在线性时间里生成“一个有限集合A的幂集P(A)”，这就说明（证明）NDTM具有在线性时间里完成“TM（DTM）必须使用指数时间”的能力。
再结合现有的大量相关研究结果，自然有：
① 对于 TM（DTM），P ≠ NP；
② 对于 NDTM（NTM），P ＝ NP。
这就完全说明了“P vs NP”的本质：
① 不同的事物（问题类），存在客观的不同难度；
② 采用不同的手段（工具），解决同一问题的时间复杂性也不一样。
所以，P和NP之间的关系，不仅仅由问题类自身的性质决定；同时还与采用的计算机模型有关！
通俗些：
一位老人去一家“私人饭馆”吃饭。要不要付钱？
答案的相对性：
① 如果该老人是“私人饭馆”老板他爹，不仅白吃，还可以打包带走更多的美食，带回去给老板的慈母吃！
② 换成是傻，吃了不给钱，肯定挨一顿臭揍！
四、交作业（2）：为什么其他证明方法都注定不成功？
成功的方法有很多种。
利用集合论，应该是最简单的一种。我自己还有另外3种成功的“弱”方法。其中“概率化”方法相当直观地说明了“P对NP”的实质。可惜，十几年过去了，一直没有精力去发表。
“大多数指数时间算法只是穷举搜索法的变种, 而多项式时间算法通常只有在对问题的结构有了某些比较深入的了解之后才能给出。”不知道这句话出处的人，没有弄清楚“P对NP”，应该不算奇怪。
历史似乎是：
第一个“正确的证明”完成后，往往后面有多如牛毛的其他证明接踵而来。
所以，
关键是“首次解决成功”，
这往往来自对问题的某种深层次认识。
几篇综述建议的方法（可惜都是只有抽象的思路），都可行。
五、交作业（3）：为什么只有我成功了？
正如《三体》里常伟思将军对汪淼院士说：
“是的，整个人类历史也是偶然，从石器时代到今天，都没什么重大变故，真幸运。但既然是幸运，总有结束的一天；现在我告诉你，结束了，做好思想准备吧。”
《中国大百科全书·数学》、《从一到无穷大》、《集合论》、《图论》，或许还应该包括《Encyclopedia of Mathematics》，是我直接用到的数学。
换做别人，只要能把这些知识放在一起，也会“偶然”地发现我的在“P vs NP，P对NP”上的发现。
真正让我失望的是：
“P vs NP，P对NP”并不需要新的数学；现有的主流权威数学是足够的。
从“P=?NP Poll”大约的确可以猜测：没有别人去阅读我上面列出的书籍。
请允许我引用大数学家阿诺德（Vladimir Igorevich Arnold, Влади́мир И́горевич Арно́льд, 1937-06-12 ~ 2010-06-03）来结束我的作业吧！
One other characteristic of the Russian mathematical tradition is the tendency to regard all of mathematics as one living organism. In the West it is quite possible to be an expert in mathematics modulo 5, knowing nothing about mathematics modulo 7. One's breadth is regarded as negative in the West to the same extent as one's narrowness is regarded as unacceptable in Russia.
俄罗斯数学传统的另一特点是倾向于全面地把数学看成一个充满活力的有机体。西方学界有可能一个人只是数学上某一方面的专家，而对相邻分支一无所知。一个学者涉猎较广在西方学界被看成一大缺点，而恰恰在俄罗斯一个学者研究领域太窄被看成同样程度的不足。
PS附言：
我故意略去相关的专业参考文献和缩写术语的全称。
这本身大约的确可以说明了“P vs NP”为什么没有被别人解决。
最后，一定要重复三遍狄利克雷：
“用清晰的思想代替盲目的计算。”
“用清晰的思想代替盲目的计算。”
“用清晰的思想代替盲目的计算。”
图3 Gregory John Chaitin 老师：我说了都 50多年了。
https://adamwalanus.pl/2016/chaitin/160519-1803-58.jpg
图4 Gregory John Chaitin 老师：你们怎么都不听啊？
https://adamwalanus.pl/2016/chaitin/160519-1839-21.jpg
图5 Chaitin 老师：我真的无话可说了。
https://adamwalanus.pl/2016/chaitin/160519-1901-45.jpg
https://adamwalanus.pl/2016/chaitin/index.html
图6 Chaitin 老师：小杨可是真不容易！
https://adamwalanus.pl/2016/chaitin/160519-1823-11.jpg
https://adamwalanus.pl/2016/chaitin/index.html
图7 Арно́льд 老师：小杨，你运气不错啊！
https://chronology.org.ru/images/thumb/d/df/VI_Arnold-03.jpg/1200px-VI_Arnold-03.jpg
图8 Арно́льд 老师：全人类都不肯去跟你争！
https://dzismis.com/wp-content/uploads/2022/10/vladimir-arnold-1200x1607.jpg
https://dzismis.com/2022/10/24/wladimir-arnold/
图9 Арно́льд 老师：我好羡慕啊！
https://cdn.fishki.net/upload/post/2020/04/26/3300060/800px-vladimir-arnold-1.jpg
https://fishki.net/3300060-shutka-arnolyda.html
图10 柯尔莫哥洛夫老师（Андре́й Никола́евич Колмого́ров, Andrey Nikolaevich Kolmogorov, 1903-04-25 ~ 1987-10-20）：
小杨，我同事说的对！我就不研究 P vs NP 了。你放手一搏吧！
https://kuzminykh.org/img/inte-2020/2312/image_bmFQ6n07dFwK4TJ.jpg
https://af.kuzminykh.org/2312-andrey-kolmogorov.html
推荐阅读：
[1] 郑波尽，2024-03-16 22:48，杨正瓴的PvsNP证明
https://blog.sciencenet.cn/blog-241229-1425614.html
参考资料：
[1] 杨东屏. 哥德尔不完全性定理剖析[J]. 曲阜师范大学学报：自然科学版,1993,19(1):31-36. 1993年1月
https://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFD&filename=QFSF199301005
http://qikan.cqvip.com/Qikan/Article/Detail?id=1140345&from=Qikan_Search_Index
[2] S. H. Lui, An Interview with Vladimir Arnol'd [J], Notices of the AMS, 1997, 44(4): 432-438.
https://www.ams.org/journals/notices/199704/index.html
[2-2] 科普中国，2022-12-08，专访数学大师阿诺德：那些年顶级数学家在莫斯科齐聚一堂
https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=389707
布尔巴基学派（Bourbakists）声称所有伟大的数学家——用狄利克雷（Peter Gustav Lejeune Dirichlet）的话来讲——是“用清晰的思想代替盲目的计算”。布尔巴基宣言中的这句话，翻译成俄语变成了“用盲目的计算代替清晰的思想”。译审是柯尔莫哥洛夫，他精通法语。我发现这一错误后大吃一惊，就去找柯尔莫哥洛夫讨论。他答道：我不觉得翻译有什么问题，翻译把布尔巴基风格描述得比他们自己说的更准确。
[3] Gregory Chaitin, Copernicus Festival, Kraków, 2016 05 19
https://adamwalanus.pl/2016/chaitin/index.html
相关链接：
[1] 2022-03-01，[科普 + 备课] Chaitin定理（1966年）
https://blog.sciencenet.cn/blog-107667-1327564.html
[2] 2022-10-19，[想不明白] 几十页、上百页长的数学证明，真的可靠吗？（阿诺德、Chaitin）
https://blog.sciencenet.cn/blog-107667-1360078.html
[3] 2020-03-20，破除论文“SCI至上”：弗拉基米尔·阿诺德1995年的几句话
https://blog.sciencenet.cn/blog-107667-1224424.html
感谢您的指教！
感谢您指正以上任何错误！
感谢您提供更多的相关资料！
![（热门）[P vs NP，讨论，交作业] 郑波尽老师：P vs NP的本 +1.jpg](http://image.sciencenet.cn/home/202403/25/140818d1irbr999651pe9p.jpg)
附录：
[1] 郑波尽，2024-03-16 22:48，杨正瓴的PvsNP证明
https://blog.sciencenet.cn/blog-241229-1425614.html
https://blog.sciencenet.cn/blog-107667-1426579.html
上一篇：边一（毛毛）兄： 请“授权”转载您的博文 《恰同学少年——因研究生时的工作获得诺贝尔奖的俊才们》
下一篇：[打听，P vs NP] 柯尔莫哥洛夫 Kolmogorov 老师为什么没有研究“ P vs NP”？
