“人是社会关系的总和,人不能脱离社会而存在。”
物质世界是“普遍联系”和“永恒发展”的。
数学是现实世界中的“数量关系”和“空间形式”的科学。
真理越辩越明。
汉语是联合国官方正式使用的 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
[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
感谢您的指教!
感谢您指正以上任何错误!
感谢您提供更多的相关资料!
转载本文请联系原作者获取授权,同时请注明本文来自杨正瓴科学网博客。
链接地址:https://wap.sciencenet.cn/blog-107667-1394724.html?mobile=1
收藏