“人是社会关系的总和，人不能脱离社会而存在。”

物质世界是“普遍联系”和“永恒发展”的。

数学是现实世界中的“数量关系”和“空间形式”的科学。

真理越辩越明。

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

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

Not to discriminate against Chinese, please!

[请教，讨论] P对NP（八）：“P对NP”为什么这么难？

   试着做一些初步的分析。

一、直观的类比

（1）实系数一元二次方程（quadratic equation），根的判别式（discriminant）< 0 时，有没有解？

   答案：

   ① 没有。初中生，在实数域；

   ② 有。高中生，在复数域。

（2）几何里的“点、线、面、体”，谁大（复杂）？

图1  点、直线、平面、立体块，谁更大（复杂）？

   直观看：从左到右，点、直线、平面、立体块，越来越大（复杂）。

   但是，借助具体的数学指标时：

   计算面积，点、直线都是0；平面一般是一个有限的数值。

   计算体积，点、直线都是0；平面也是0。

   依据不同的指标，得到的结论也不同。

   平面是否和直线一样复杂？这差不多是“P对NP”的一个直观的类比。

   演绎推理的结论是前提蕴含的。

二、P对NP

（1）P 包含于 NP, 即 P ⊆ NP ，是一种定量的“大小”的关系。

   P ＝ NP ，或者 P ≠ NP ，都是是一种定性的“二值”符号。

   因此，无法将“P 包含于 NP”直接转化为“P ＝ NP 或 P ≠ NP”。要想实现这种转化，一种方便的方法就是设定“指标的阈值”，类似“面积、体积”。并且采用不同的“指标的阈值”，转化的结果也不同。

   用“多项式复杂性”作为“指标的阈值”：P ≠ NP。

   用“指数复杂性”作为“指标的阈值”：P ＝ NP。

   这并不否认 P 和 NP 之间的客观性差别。实际上，NTM 相当于 DTM 的幂集，存在“不同”这种客观的差别。

   表达这种“客观的差别”的主观标准不同，导致了逻辑结论的差别。

（2）作为文化背景，过于看重“逻辑”、“丘奇论题 Church-Turing Thesis”等，可能误导或干扰了“P对NP”的研究。

   假如庞加莱遇到“P对NP”，大概算不什么大事。

图2  （美）玛莎·葛森著. 完美的证明 一位天才和世纪数学的突破[M]. 2012 page 153 截图

   假如希尔伯特不搞他的 Hilbert’s Program，遇到“P对NP”，大概也算不什么大事。

   可惜，历史不能假设。

   庞加莱：逻辑是证明的工具，直觉是发明的工具。逻辑可以告诉我们走这条路或那条路保证不遇见任何障碍，但是它不能告诉我们哪条道路能引导我们到达目的地。为此必须从远处瞭望目标，教导我们瞭望的本领的是直觉。没有直觉，数学家就会像这样一个作家，他只会按语法写诗，但是却毫无思想。

   像爱因斯坦一样，庞加莱很清楚“逻辑方法的局限性”！！庞加莱会轻而易举地彻底解决“P对NP”。

   希尔伯特：数学知识终究要依赖于某种类型的直觉洞察力。

参考资料：

[1] Jules Henri Poincaré, MacTutor History of Mathematics archive

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

[2] David Hilbert, MacTutor History of Mathematics archive

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

[3] Hilbert’s Program - Stanford Encyclopedia of Philosophy

https://plato.stanford.edu/entries/hilbert-program/#3

[4] 2022-01-20，形式主义/formalism/刘叶涛，中国大百科全书，第三版网络版[DB/OL]

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

   数学基础和数理逻辑研究中的三大派别之一。

   代表人物有D.希尔伯特、P.I.贝尔纳斯、W.F.阿克曼、J.冯·诺伊曼和G.根岑等。形式主义是从希尔伯特纲领和元数学研究发展而来的。1904年，希尔伯特在第3届国际数学家大会上发表讲演，首次提出要用公理化方法为算术规律和逻辑规律奠基，同时首次提出应该把证明本身也作为研究对象。这就是希尔伯特的证明论纲领。

[5] 2023-01-18，数学基础/foundations of mathematics/何浩平，中国大百科全书，第三版网络版[DB/OL]

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

   同时发展出的公理集合论成为了事实上的数学基础。

   20世纪初数学基础研究的结果，是数学家们在实践中接受了公理化的集合论作为经典数学的基础。

   E.F.F. 策梅洛、A.A.弗伦克尔（Adolf Abraham Fraenkel）等人发展出的ZFC（策梅洛-弗伦克尔-选择公理）公理集合论，是今天通行的公理集合论。ZFC公理集合论是万有理论，能够推导出经典数学的所有理论。

[6] 2022-01-20，逻辑/logic/周礼全、诸葛殷同撰，杜国平修订，中国大百科全书，第三版网络版[DB/OL]

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

   研究推理有效性的学问。

   逻辑一般从推理形式的角度来研究推理的有效性问题。”

一些近年的参考文献：

[1] Lance Fortnow. Fifty years of P vs. NP and the possibility of the impossible [J]. Communications of the ACM, 2022, 65(1): 76–85.

doi:  10.1145/3460351

https://m-cacm.acm.org/magazines/2022/1/257448-fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/fulltext?mobile=true

[2] Jorge A. Ruiz-Vanoye, Ocotlán Díaz-Parra, Francisco Rafael Trejo-Macotela, Julio Cesar Ramos-Fernández. Editorial: P versus NP problem from formal languages theory view [J]. International Journal of Combinatorial Optimization Problems and Informatics, 2021, 12(1): 1-8. Jan-April 2021

https://webdesignwaterloo.net/all-p-problems-are-np-problesm-scholarly-articles

[3] Luciana S. Buriol, Celina Figueiredo, Mauricio G. C. Resende, Eduardo Uchoa. The guide to NP-completeness is 40 years old: an homage to David s. Johnson [J]. Pesquisa Operacional, 2020, 40: e236329, 1-11

doi:  10.1590/0101-7438.2020.040.00236329

https://www.scielo.br/j/pope/a/Cw4K8K374SySpJdNdx9kPLx/?lang=en

[4] Juraj Hromkoviˇc, Peter Rossmanith. What one has to know when attacking P vs. NP [J]. Journal of Computer and System Sciences, 2020, 107: 142-155. February 2020

doi:  10.1016/j.jcss.2019.06.004

https://www.sciencedirect.com/science/article/pii/S0022000019300558

[5] Igor L. Markov. Limits on fundamental limits to computation [J]. Nature, 2014, 512((7513): 147-154.

doi:  10.1038/nature13570

https://www.nature.com/articles/nature13570

[6] Lance Fortnow. The Status of the P Versus NP Problem [J]. Communications of the ACM, 2009, 52(9): 78-86. 

doi:  10.1145/1562164.1562186 

https://m-cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

发表的论文：

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

doi:  10.1007/s12209-011-1593-5

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

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

doi:  10.3969/j.issn.1673-5692.2011.04.009

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

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

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

[4] 人脑有多复杂？[J]. 百科知识, 1997, 7(总第216期): 39-40.

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

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

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

相关链接：

[1] 2023-07-08，[请教，讨论] P对NP（七）：“形转换”与立体图、平面图

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

[2] 2023-07-07，[请教，讨论] P对NP（六）：无穷化版本与连续统假设CH

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

[3] 2023-07-05，[讨论] P对NP（五）：宇宙“热寂”之前，“幂集公理”不会有太大的毛病？

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

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

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

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

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

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

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

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

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

[8] 2023-01-16，[搞笑？搞哭？汇集] 怎样判断“原创”和“诺贝尔奖成果”？

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

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

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

感谢您的指教！

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

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