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

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

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

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

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

Not to discriminate against Chinese, please!

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

核心：“P对NP”问题与“无穷”之间无任何关系

术语：

P对NP： P vs NP, P versus NP

确定型图灵机： DTM, deterministic Turing machine

非确定型图灵机： NTM, non-deterministic Turing machine

集合论： set theory

无穷： infinity

无穷公理： axiom of infinity

策梅洛-弗兰克尔集合论： ZFC, Zermelo–Fraenkel set theory with the axiom of choice

由“幂集公理”可以发现：NTM 相当于 DTM 的幂集。

图1  “P对NP”与主要的后续观点

一、按时间顺序

1.1  “P对NP”是 ZF 里幂集公理的一个具体表现

   1993年暑假发现了“形转换”。既然“P对NP”从“数”的角度一直说不清楚，就转换到“形”的角度看看吧！

   3SAT里可以包含诸多库拉托夫斯基图（Kuratowski graphs）K_3,3、K₅，这样就可以充分性地形成指数方式增加的复杂性了。

   这就是“P对NP”的答案？连我自己都不敢相信。尽管是真的。别人肯定不相信的！！

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

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

   恰好我又知道“哥德尔不完全性定理”。还有那个似懂非懂的“柴庭定理 Chaitin theorem”。

   于是，找个“能力大”的数学系统来继续考察“P对NP”吧！

   《中国大百科全书·数学》里说：“集合论是整个数学的基础”。那就从策梅洛-弗兰克尔集合论开始吧！看到里面的“幂集公理 Axiom of power set”，我开始怀疑人生：“P对NP”这么简单！还需要证明吗？

   《中国大百科全书》第三版里说：“ZFC公理集合论是万有理论，能够推导出经典数学的所有理论。”

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

1.2  用“连续统假设”去吓唬别人！ 

   为了故作高深，必须把“P对NP”复杂化！“拉大旗作虎皮，包着自己，去吓唬别人。”（鲁迅《且介亭杂文末编·答徐懋庸并关于抗日统一战线问题》）

   我恰好拜读过克莱因教授的《古今数学思想》（Morris Kline. Mathematical Thought from Ancient to Modern Times），自然知道“无穷”的争议。但是，实在没办法，为了“去吓唬别人”，只能“无穷化”了！

   “凡是拿无穷说闲话的，只要给他们套一个‘非主流的’紧箍咒，料他们就不敢多言语了。”“哪个敢来找麻烦，就给他戴一顶‘民科’的帽子！”

   要是有人对ZF里的“幂集公理”说闲话，怎么办？这个就不用我操心了：我们地球人会一致认为TA是外星人的！

   放心吧！

   将 DTM、NTM 无穷化，它们的基数分别是 a、c。

   于是 NPI（NP-intermediate）就成了康托原本意义下的“连续统假设 Continuum hypothesis”。这要用到“选择公理 axiom of choice”、“无穷公理 axiom of infinity”。要是有人说闲话怎么办？那就说TA们“非主流、民科”吧！

   要是“无穷公理 axiom of infinity”真的有问题，怎么办？好在“幂集公理”不会有毛病的。

   时间已经到了大约 1993年底。

1.3  概率化 

   “幂集公理”，在我们这些地球人“两脚一蹬，死翘翘”之前，不会“错”的。不仅仅是现代数学家们这么看，就连古时候的老子、孔子老师，也都有这个意思。

   “幂集公理”的实质：不同事物之间，是有数量、质量等方面差别的；不宜把不同的事物都“混为一谈，等量齐观”。

   这个看法，今后十亿年之内不会有明显错误的。甚至“正确”到地球毁灭之日！！

   于是我放心了。就去思考“磁场、电磁波会不会依赖参照系”等其它事情了。

   到了大约 2010年，忽然又想起“完全图上的哈密顿路有指数多个 undirected Hamiltonian paths on complete graph K_n is (n-1)!/2”。于是又提出P对NP的“概率化”方法：这样显得更直观点。

图2  “P对NP”与“无穷”的关系

由“幂集公理”可以发现：NTM 相当于 DTM 的幂集，有穷。

二、“P对NP”之后

   1993年底之时，考虑到“对于NP完备问题，指数时间是必须的”。遇到更复杂的问题给怎么办？只能寻找更有力的工具了。

   人脑到底有多复杂？

   我只能“主流”地采用ZFC了。康托无穷级数第二序列，是幂集公理无穷化后的结果，和“有理数”、“实数”等概念之间有良好的衔接，于是采用了这个方法。

2.1  人脑的复杂性

   人类可以有意识地“手舞足蹈”：这是“几何曲线”的自由组合，是康托无穷级数第二序列里的第4个元素。这意味着，人类可以方便地处理“几何曲线”。这个看法有实验心理学的结果支持：也就是斯佩里（Roger Wolcott Sperry）1981年诺贝尔生理或医学奖的得奖原因，左右脑的认知功能。

   经过不断努力，1997年，有了《百科知识》杂志的“人脑有多复杂？”一文。

2.2  第2类数域

   既然人脑复杂性不低于第4个元素，并且实数是第2个元素，那么自然存在“人脑能够快速处理的，并且比实数更复杂的数”，该数对应第3个元素。实际上，人类和动物的视觉，就是这种以“几何曲线”为基本元素的信息处理。当时已有几何光学的4f系统！

   那就放心大胆地发展这种以“几何曲线”为基本元素的数学吧！好像是1997年干的？应该是确信“人脑复杂性的估计”有充分的历史积淀之后。

   显然易见，将实数扩充到一般的几何曲线，就得到了“第2类数域”，可以建立“第2类计算机”的理论模型。

   （1）图灵的计算机，是“第0类”的；

   （2）大数学家 Smale 等人的“实数环上的计算机”，是“第1类”的；

   （3）以几何曲线为单元的计算机，是“第2类”的；

   （4）人脑，至少是“第3类”的；

   （5）集体智慧，属于“第4类”的；

   ……

   这是 1999年《哲学研究》那篇论文的观点。

2.3  没有时间、没有精力

   之后，就是“没有功夫吃饭、没有功夫睡觉”了。

三、“P对NP”之后：三类数学观点

3.1  演绎证明的相对性、完全证明

   演绎证明的结论，是其前提蕴含的。

   采用不同的“证明系统”，对同一问题会得到不同的演绎证明结果。

   “非欧几何”，就是以前的一个典型例子。

   “P对NP”，再次揭示了演绎证明的性质：前提蕴含。因此，对于重大的数学基础问题，应尽可能采用“完全证明”，尽可能透彻地搞清楚问题的实质。

3.2  几何曲线，可以构成“第2类数域”

   不仅直接证明了“数学是现实世界中的数量关系和空间形式的科学”，即“数”、“形”之间的统一，还是对 1872年“埃尔朗根纲领”的直接发展。

   数学里“数”、“形”之间的统一，一个可能的框架就是“第2类数学”。

3.3  人脑复杂性估计

   一般认为：思维之谜，是继哥白尼日心说、达尔文进化论之后的第三次科学革命。

   我们的“人脑复杂性估计”，尽管没有解决“思维之谜”，但足以有充分历史积淀地说明了人脑在宇宙中的地位。

   感谢美国数学会会士 Judith Victor Grabiner 教授 1986年的“Computers and the nature of man: a historian's perspective on controversies about artificial intelligence”一文！

   “Throughout history, developments in the sciences have caused people to change their views of man and his place in the universe. The Copernican Revolution placed man on a planet, adrift in space; the Darwinian Revolution changed our view of human origins. Computers, too, raise questions about the nature of man: can computers think the way we do, and, if so, are we—like them—just thinking machines?【机器翻译】纵观历史，科学的发展使人们改变了对人及其在宇宙中地位的看法。哥白尼革命把人类安置在一个漂浮在太空中的星球上；达尔文革命改变了我们对人类起源的看法。计算机也提出了关于人的本性的问题：计算机能像我们那样思考吗？如果是的话，我们和它们一样只是思考机器吗？”

   由于上面这个文章，我直接从数字计算机跨越到了人脑！它是继哥白尼日心说、达尔文进化论之后的第三次科学革命啊！我不能解决思维之谜，但我可以给人脑在宇宙中的位置进行定位啊！

图3  美国数学会会士 Judith Victor Grabiner 教授

https://www.pitzer.edu/academics/wp-content/uploads/sites/38/2014/12/FAC-Judy-Grabiner.jpg

https://www.pitzer.edu/academics/faculty/judith-grabiner/

https://www.ams.org/cgi-bin/fellows/fellows.cgi

Grabiner, Judith Victor, Pitzer College - 2013, Inaugural Class of Fellows

后记

   2000年5月24日在巴黎法兰西学院举行的一次会议上（a meeting in Paris, held on May 24, 2000 at the Collège de France），美国马萨诸塞州剑桥克莱数学研究所（The Clay Mathematics Institute of Cambridge, Massachusetts, CMI）宣布设立了七个奖问题，即千禧年问题（The Millennium Prize Problems），

https://www.claymath.org/millennium-problems/

其中之一是“P vs NP”，https://www.claymath.org/millennium/p-vs-np/

   幸亏在这之前我找不到地方“正式”发表我的思考。

   尽管 1995年我有3次发表的证据：天津大学百年校庆研究生院、自动化学院的学术报告会，以及更早的“挑战杯”参赛论文。

   1995年前后参赛“挑战杯”的论文，我后来有点拿不准了。是善良的好人们提醒我回忆出的。感谢并祝福这些好人们！

参考资料：

[1] Mathematics. Encyclopedia of Mathematics.

https://encyclopediaofmath.org/wiki/Mathematics

[2] Weisstein, Eric W. "Hamiltonian Cycle." From MathWorld--A Wolfram Web Resource.

https://mathworld.wolfram.com/HamiltonianCycle.html

[3] Roger Sperry. Some effects of disconnecting the cerebral hemispheres [J]. Science, 1982, 217(4566): 1223-1226. 

DOI: 10.1126/science.7112125

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

[4] 沈惠川，2013-01-24，华飞：哥本哈根三人组在商量什么？（沈惠川改编)

https://blog.sciencenet.cn/blog-605880-656115.html

   玻尔：“这就用不着我们操心了。我们两脚一蹬，功成名就！我画一个太极图，就够他们琢磨一辈子了。天下理论物理学家，尽入我彀内。凡是说量子力学闲话的，只要给他们套一个‘经典的’紧箍咒，料他们就不敢多言语了。学生嘛，凡是说听不懂的，都不让及格！这样若干年以后，就都是我们的人了。”

   海森伯：“听闻中国有‘民科’一说。哪个敢来找麻烦，就给他戴一顶‘民科’的帽子！虽然中国的‘民科’是反对相对论的，但是我们可以抓住相对论当作挡箭牌，气死老爱因斯坦。”

   泡利：“够损！”

[5] Roger W. Sperry, The Nobel Prize in Physiology or Medicine 1981

https://www.nobelprize.org/prizes/medicine/1981/sperry/facts/

https://www.nobelprize.org/prizes/medicine/1981/summary/

[6] Lenore Blum, Mike Shub, Steve Smale. On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines [J]. Bulletin (New Series)o of the American Mathematical Society, 1989, 21(1): 1-46.

doi:  10.1142/9789812792839_0013       Volume 21, Number 1, July 1989

https://www.ams.org/journals/bull/1989-21-01/S0273-0979-1989-15750-9/

https://www.ams.org/journals/bull/1989-21-01/S0273-0979-1989-15750-9/S0273-0979-1989-15750-9.pdf

DOI: 10.1109/SFCS.1988.21955

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

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=21955

[7] 2022-12-23，埃尔朗根纲领/Erlangen program/几何学分支，中国大百科全书，第三版网络版[DB/OL]

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

[8] Judith Victor Grabiner. Computers and the nature of man: a historian’s perspective on controversies about artificial intelligence [J]. Bulletin of the American Mathematical Society, 1986, 15(2): 113-126.

doi： 10.1090/S0273-0979-1986-15461-3   

https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-15/issue-2/Computers-and-the-nature-of-man--a-historians-perspective/bams/1183553467.full

相关链接：

[1] 2023-06-28，[补充扼要说明] “P对NP, P vs NP”问题的“1+3”种证明与无穷

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

[2] 2023-06-27，[请注意] “P对NP, P vs NP”问题与“无穷 infinity”无关

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

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

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

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

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

[5] 2020-08-17，小忆“第2类数学（智能数学）”的提出

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

[6] 2010-08-27，11年前的记忆：人脑复杂性的估计及其哲学意义

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

感谢您的指教！

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

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