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

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

Not to discriminate against Chinese, please!

[随笔] “P对NP, P vs NP, P versus NP” Problem 问题：问题与求解方法

求教心切，由于种种原因，下文里面错误难免。

请您不吝批评与指教！衷心感谢！

Key words:  P vs NP Problem,  The P versus NP Problem,  polynomial-time,  NP-complete,  NP-completeness,  set theory,  Zermelo–Fraenkel set theory,  ZF,  axiom of power set,  independence

   一些要点笔记。没有精力和时间细说。

一、“P对NP, P vs NP, P versus NP” Problem 问题的直观描述

   However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

   P（即容易找到）和NP（即容易检查）问题。

   http://claymath.org/millennium-problems/p-vs-np-problem

   除了斯蒂芬·库克的官方问题描述《P对NP问题》（Stephen Cook, Official Problem Description, The P versus NP Problem）之外，《Computers and Intractability: A Guide to the Theory of NP-completeness》也是比较全面的介绍。

二、“P vs NP Problem”结果相对化的必然性

2.1  问题求解的难易性，实际上是由“问题”和“求解工具”双方的关系决定的

   工欲善其事，必先利其器。

   没有金刚钻，别揽瓷器活。

   难者不会，会者不难。

图1  “问题”和“求解工具”：谁更大？

2.2  对数学基础的一个重要的启发

   用“更小的差别”来取代“幂集公理 Axiom of power set”，可能对导致“更好”的集合论公理系统。

   例如，改用“多项式公理 Axiom of polynomial”，该公理可以推导出“幂集公理 Axiom of power set”。

   大学一年级工科本科生，在《高等数学》里都学过“∞/∞”的极限运算。“多项式/指数”和“低阶多项式/高阶多项式”，都存在极限“无穷小”。

   加强集合论能力的一个具体工作，就是用“更小的差别”来取代“幂集公理 Axiom of power set”。寻找比多项式更小的独立关系。

   这里的独立，是指与“多项式/根式”、“指数/对数”关系有较为明显差别的新关系。并且由此新关系，可以推导出（蕴含）“幂集公理 Axiom of power set”。

三、“P vs NP Problem”研究中可能的障碍

（1）不愿意研究

   当今世界范围的岗位聘任、短期考核等，迫使大家难以或无法去研究重大问题。

   新华网，2019-10-11，日本迎来“诺奖热潮” 从科学到工程获奖领域广泛

http://www.xinhuanet.com/world/2019-10/11/c_1210307397.htm

https://baijiahao.baidu.com/s?id=1647107383699397810&wfr=spider&for=pc

http://news.china.com.cn/2019-10/11/content_75290207.htm

   从过去情况看，获得诺奖的成果大多是研究人员25至45岁取得。在当前日本的大学和研究机构，对20岁至39岁的年轻研究人员大多采用聘用制。研究人员追求短期成果，难以作出大胆挑战和踏实从事基础研究。

   正如丘成桐老师所说：

   “可是你真要做一个好的题目，其实也不见得那么难，…，并不是想你想象得要花很多能多时间，问题是你的决心怎么样。” 完成一个好题目，也就是差不多完成三个小题目的时间和精力。

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

刘全慧，2020-09-22，开学第一课，丘成桐给大学生指出一条成材捷径

   2019年12月获得诺贝尔化学奖的旭化成公司名誉研究员吉野彰也有同样的危机感。身为企业人的诺奖得主吉野在很多场合都强调：“没有失败就绝对不会成功”、“对年轻研究人员来说，至少需要保证10年以上的研究时间，希望能打造一个按照自己的想法如愿开展研究的环境”等。

https://www.keguanjp.com/kgjp_keji/kgjp_kj_etc/pt20200221000002.html

泷川 进，2020-02-21，【日本的科技政策】（十）“选择与集中”得到的与失去的

（2）丘奇-图灵论题（Church-Turing Thesis），可能误导了 “P vs NP” 的研究

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

   直至今日丘奇论题仍为绝大多数数理逻辑学家所承认。同时也一般地认为，丘奇论题不能在数学理论里证明，不是一个数学定理。它只是说明，某些数学理论是一特定直观概念的严格的数学描述。——引用自王宪钧《数理逻辑引论》，第367页

   丘奇论题并不直接和“P vs NP”相关，但作为相关的知识背景，有可能以潜在的方式误导对“P vs NP” 的研究。

   丘奇-图灵论题，是“希尔伯特的形式化方案”的一个具体应用，依然信奉“万物平等”这个片面性的信念。当在实践中“P vs NP”被观察到时，有关的“证明”没有找到“不平等”的具体工具，所以一直证明不出来。哥德尔、Chaitin 的定理，实质上是反对“丘奇-图灵论题”的。其实 Chaitin 定理已经说得再清楚不过了。

（3）数学-科学视野

   正如阿诺德 1995年所言：

   “俄罗斯数学传统的另一特点是倾向于全面地把数学看成一个充满活力的有机体。西方学界有可能一个人只是数学上某一方面的专家，而对相邻分支一无所知。一个学者涉猎较广在西方学界被看成一大缺点，而恰恰在俄罗斯一个学者研究领域太窄被看成同样程度的不足。”

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

2020-03-20，破除论文“SCI至上”：弗拉基米尔·阿诺德1995年的几句话

   我知道“数学”的一个常见定义：

   一般地，“数学是研究现实世界中数量关系和空间形式的，简单地说，是研究数和形的科学。”（吴文俊，《中国大百科全书·数学卷》）。这根源于***：“纯数学的对象是现实世界的空间形式和数量关系，所以是非常现实的材料．这些材料以极度抽象的形式出现，这只能在表面上掩盖它起源于外部世界的事实．但是，为了能够从纯粹的状态中研究这些形式和关系，必须使它们完全脱离自己的内容，把内容作为无关重要的东西放在一边；这样，我们就得到没有长宽高的点、没有厚度和宽度的线、a和b与x和y，即常数和变数；只是在最后才得到悟性的自由创造物和想象物，即想象的数量．甚至数学上各种数量的明显的相互导出，也并不证明它们的先验的来源，而只是证明它们的合理的相互关系．”

   The science of quantitative relations and spatial forms in the real world. Being inseparably connected with the needs of technology and natural science, the accumulation of quantitative relations and spatial forms studied in mathematics is continuously expanding; so this general definition of mathematics becomes ever richer in content.

   现实世界中数量关系和空间形式的科学。由于与技术和自然科学的需求密不可分，数学中研究的数量关系和空间形式的积累在不断扩大；因此，数学的一般定义在内容上变得越来越丰富。

https://encyclopediaofmath.org/wiki/Mathematics

Mathematics. Encyclopedia of Mathematics.

（4）过于实际

   没有从这个问题的实际起源中超脱出来，将其“理直气壮”地看成一个“纯粹”的数学问题。

   这就失去了和 ZF（Zermelo–Fraenkel set theory）联系在一起的机会。

   似乎全世界只有我注意到了这点。

（5）之后是对数学“演绎证明”基本性质的关注

   似乎忘记了2000多年之前古希腊的“苏格拉底必定会死”。

   演绎逻辑证明的实质：前提蕴含。

   没有注意到 Chaitin 定理提供的强大思路：去找最基础的数学理论《集合论》！！

   似乎全世界只有我注意到了这点。

（6）“问题”和“求解工具”之间的关系

   NDTM 和 DTM，工具不同，“P vs NP”问题的答案也会不同。

   仅仅研究该“问题”自身，必然导致结果的不确定性。

   “天下没有免费的午餐”？

   小学生回家吃午餐，免费是正常的！

   在演绎逻辑证明中，不同的前提蕴含了不同的结论。

参考资料：

[1] P vs NP Problem , Clay Mathematics Institute

http://claymath.org/millennium-problems/p-vs-np-problem

http://claymath.org/millennium-problems

[2] Charles Seife. What Are the Limits of Conventional Computing? [J]. Science, 2005, 309(5731): 96-97.

DOI:  10.1126/science.309.5731.96

https://www.science.org/doi/10.1126/science.309.5731.96

[3] 季铮锋, 夏盟佶. 计算的极限[J]. 科学通报, 2016, 61: 404–408

doi:  10.1360/N972015-01363

https://www.sciengine.com/CSB/doi/10.1360/N972015-01363

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

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

[6] 王宪钧. 数理逻辑引论[M]. 北京：北京大学出版社，1982.

[7] S. H. Lui, An Interview with Vladimir Arnol'd [J], Notices of the AMS, 1997, 44(4): 432-438

http://www.ams.org/notices/199704/arnold.pdf

https://www.ams.org/journals/notices/199704/index.html

[8] Gregory John Chaitin. Information-theoretic computation complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15.

DOI: 10.1109/TIT.1974.1055172

https://ieeexplore.ieee.org/document/1055172

https://dl.acm.org/doi/10.1109/TIT.1974.1055172

[9] 中国大百科全书·数学[M]. 北京：中国大百科全书出版社，1988.

[10] Church thesis. Encyclopedia of Mathematics. [ED/OL]

https://encyclopediaofmath.org/wiki/Church_thesis

   A principle according to which the class of functions computable by means of algorithms in the broad intuitive sense (cf. Algorithm), coincides with the class of partial recursive functions. Church' thesis is this fact of nature, which is confirmed by the experience accumulated in mathematics throughout its history. All known examples of algorithms in mathematics satisfy it. The thesis was first formulated by A. Church (1936). Each different precise definition of the intuitive notion of algorithm corresponds to its own version of Church' thesis. Turing's thesis is the assertion that every function that is computable in the intuitive sense is computable by some Turing machine, and Markov's normalization principle says that any function that is computable in the intuitive sense is computable by some normal algorithm. From the equivalence of the known definitions of the notions of algorithm, it follows that the various forms of Church' thesis are equivalent. This fact is yet another confirmation of Church' thesis. The thesis of Church cannot be strictly proved, since its formulation involves the inexact notion of "algorithm in the intuitive sense" . There were attempts to refute Church' thesis, but they have not led to success (1984). The acceptance of Church' thesis is useful in the theory of algorithms and its applications. First, in proving the existence of an algorithm of one kind or another — Turing machines, recursive functions, normal algorithms, and others — one may, by virtue of Church' thesis, restrict oneself to intuitively obvious constructions, and need not write out the corresponding formal scheme.

   丘奇的论点不能被严格证明，因为它的表述涉及“直觉意义上的算法”这一不精确的概念。有人试图反驳丘奇的论点，但并没有成功（1984年）。

我的相关资料：

[1] Zhengling Yang (杨正瓴). A non-canonical example to support P is not equal to NP [J]. Transactions of Tianjin University, 2011, 17(6): 446-449.

10.1007/s12209-011-1593-5

https://link.springer.com/article/10.1007/s12209-011-1593-5

[2] 杨正瓴. 第二类计算机构想 [J]. 中国电子科学研究院学报, 2011, 6(4): 368-374.

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

http://www.cqvip.com/QK/87495A/201104/39096952.html

[3] 杨正瓴. 密码学与非确定型图灵机[J]. 中国电子科学研究院学报, 2008, 3(6): 558-562.

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

https://www.cnki.com.cn/Article/CJFDTOTAL-KJPL200806001.htm

[4] 杨正瓴，林孔元. 人类智能模拟的“第2类数学（智能数学）”方法的哲学研究 [J]. 哲学研究，1999, (4): 44-50.

http://www.cqvip.com/QK/80454X/199904/1002190349.html

https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CJFD&dbname=CJFD9899&filename=ZXYJ199904005&uniplatform=NZKPT&v=U2NoQ2MkdWD_X8dTl-dM8-9uPc4sVdZtB_SlYn-0FW3XglcR1pEBprer90wK0aYx

[5] 杨正瓴. 人脑复杂性的估计及其哲学意义[M]，《中国新时期社会科学成果荟萃》，1999，第1卷p296。卢继传 主编，中国经济出版社，北京，ISBN 7 – 5017 – 4100 – X/G. 374，（第2编，哲学，第4章，自然辩证法）.

[6] 杨正瓴. 人脑有多复杂？[J]. 百科知识，1997，7（总第216期）：pp39 – 40.

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

[7] 杨正瓴. 从NP结构到超级计算机分类理论 [R]. 天津大学百年校庆研究生院研究生学术报告会（一等奖论文），和天津大学百年校庆自动化系学术报告会，1995年10月.

相关链接：

[1] 2023-01-17，[说明] 我对“P对NP”的所有研究，使用的都是现有的主流数学理论

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

[2] 2022-06-10，[请教] P对NP（二）：结果的相对性与“1+3”种证明

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

[3] 2015-05-22，The kernel of "P vs NP Problem": Axiom of power set!

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

[4] 2012-03-23，[请教] P对NP：请***教授等专家指教（一）

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

[5] 2011-09-15，A FULL PROOF to the P versus NP problem

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

感谢您的指教！

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

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