[P vs NP，趣闻，困惑] 2023年：GPT-4成功得出 P≠NP？ （关联：演绎推理的局限性）

P对NP： P vs NP, P versus NP problem

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

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

集合论： set theory

策梅洛-弗兰克尔集合论： ZF, Zermelo–Fraenkel set theory

幂集： power set

幂集公理： axiom of power set

数学基础： foundations of mathematics

一、新智元，2023-09-14，GPT-4成功得出P≠NP，陶哲轩预言成真！97轮「苏格拉底式推理」对话破解世界数学难题

https://mp.weixin.qq.com/s/FEt0iutSkbFgd1n4AwdFmw

   最近，微软亚洲研究院、北大、北航等机构的研究人员，通过97个回合的「苏格拉底式」严格推理，成功让GPT-4得出了「P≠NP」的结论！

   古希腊哲学家苏格拉曾说过，「我不能教会别人任何事，我只能让他们思考」。

   研究人员恰巧就从中汲取了灵感，提出一种通用问题的解决框架——苏格拉底式推理（Socratic Reasoning）。

   「苏格拉底式推理」有5种强大的提示模式：演绎、转换、分解、验证、整合。

二、苏格拉底自己，同意“苏格拉底式推理”吗？

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

   这些前提，又是从哪里来的？

   所以，这些“苏格拉底式推理 Socratic Reasoning”是不是“一种巨大的同义反复”？

   必须指出的是，无效推理虽然不是完全无效的，但由于它的结论不具有必然性，因而与有效推理即必然性推理就有了本质的区别。

   以此为界限，现代逻辑将推理一分为二：必然性推理与或然性推理。

   必然性推理即演绎推理，或然性推理即归纳推理。因此，演绎推理的定义是：演绎推理就是前提与结论之间有必然性联系的推理。前提与结论之间有必然性联系即前提蕴含结论，因此，这一定义也可以等价地表述为：演绎推理就是前提与结论之间有蕴含关系的推理。

   所谓有效性，是指当前提为真时，结论不可能假，即前提真，结论必真，也就是说-个正确的演绎推理能保证从真前提得出真结论。演绎推理为什么会具有这种“保真性”？它为什么是一种“安全的”推理工具？一个现存的解释是演绎推理的结论早已包含在前提之中了，实际上是已知的，推理过程只不过是把前提中隐含的信息明朗化，是对前提中已有内容的某种重复。因此，演绎推理推不出新知识。

   这一解释是有一定道理的。但演绎推理推不出新知识却是一个引起争议的问题，这里的关键是如何定义“新知识”，如果把新知识理解为逻辑上的，即前提中没有包含的超出了前提范围的知识，那么演绎推理不能提供这样的知识。如果把新知识理解为心理上的，即隐含在前提中的尚未进人理智范围的陌生知识，那么演绎推理能够提供这样的知识。实际上，有些知识隐藏得如此之深”，以至于不通过逻辑分析和演绎推理就无法揭示出来。

吴炜，程本学，李珍编著. 自然辩证法概论[M]. 2019，第 122-123 页

图1  吴炜，程本学，李珍编著. 自然辩证法概论[M]. 2019 第123页

三、困惑：P≠NP？

   将“P对NP, P vs NP, P versus NP”当做一个纯粹的数学问题，不难发现：

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

   According to "the axiom of power set" in ZF, a NTM is equipotent to the power set of its corresponding DTM.

附录：庞加莱担心的“一种巨大的同义反复”

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

   “数学科学的可能性本身似乎就是一个无法解决的矛盾。”早在一个多世纪以前，亨利庞加莱这位被称为“最后的通才”的数学家就如是写道。庞加莱取得这个称号源于他对数学所有领域的精通。如果研究的对象仅限于想象，“那么从何衍生出这一无人能置疑的完美推断呢”？当形式逻辑的法则取代了实验的证明，“数学如何没有沦为一种巨大的同义反复”？最后，”是否我们得承认……所有这些连篇累牍中出现的各种定理仅仅只是关于A即是A的间接表达”？

   庞加莱继续解释说，数学之所以是一门科学是因为它的推理过程是从特殊到一般。一位运用足够的严谨来进行思维实验的数学家，所推导出的法则可以统领他与其他数学家共享的其他想象领域。换言之，它不仅证明了A即是A，而且还解释了是什么使A在本质上是一个A，在哪可以发现其他的A或者如何建构其他的A。

参考资料：

[1] 2024-12-03，计算复杂性/computational complexity/陆品燕，中国大百科全书，第三版网络版[DB/OL]

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

[2] 2025-04-30，复杂性类/complexity class/刘田，中国大百科全书，第三版网络版[DB/OL]

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

[3] 2022-07-13，策梅洛-弗兰克尔集合论/Zermelo-Fraenkel set theory/杜国平，中国大百科全书，第三版网络版[DB/OL]

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

[4] A history of set theory, 1996-02, MacTutor History of Mathematics

https://mathshistory.st-andrews.ac.uk/HistTopics/Beginnings_of_set_theory/

[5] Zermelo-Fraenkel Set Theory (ZF), 2023-01-31, Stanford Encyclopedia of Philosophy

https://plato.stanford.edu/entries/set-theory/ZF.html

https://plato.stanford.edu/entries/set-theory/index.html

[6] 新智元，2023-09-14，GPT-4成功得出P≠NP，陶哲轩预言成真！97轮「苏格拉底式推理」对话破解世界数学难题

https://mp.weixin.qq.com/s/FEt0iutSkbFgd1n4AwdFmw

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

doi：10.3969/j.issn.1673-5692.2011.04.009

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

https://mall.cnki.net/magazine/Article/KJPL201104010.htm

https://www.cqvip.com/doc/journal/955236059?sign=bf3d431e05ce4ae99016e1707556a5d79ad0f8b1e2508e1ab78768a9582a7393&expireTime=1789563877934&resourceId=955236059

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

https://doi.org/10.1007/s12209-011-1593-5

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

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

doi:  10.3969/j.issn.1673-5692.2008.06.002

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

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

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

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

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

[12] 杨正瓴，2011-08-30 23:51，“P对NP”难题研究的形转换新思路，中国科学院，科学智慧火花

https://idea.cas.cn/zhhh/sxwlhxytw/sx/info/2011/479662.html

以前的《科学网》相关博文链接：

[1] 2024-01-25 22:49，[优先权？] “P对NP”已经解决。 The P vs NP (P versus NP) has been solved

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

[2] 2025-04-27 22:32，[请教，往日] P对NP（二）：思考 P vs NP 的几个关键事件点

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

[3] 2024-12-25 22:49，[打听] “一个数学问题的算法复杂性的P与NP分类(多项式时间算法与非多项式时间算法)没有绝对性”的出处

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

[4] 2024-07-04 22:46，[P vs NP，Millennium Prize，科普] William Gasarch 老师的 3 次“ P=?NP Poll ”

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

[5] 2024-04-28 22:52，[资源，统一场，P vs NP] 何为相等？

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

[6] 2024-04-12 22:27，[P vs NP，数学文化] “排序 sorting”的信息论下界与“P对NP, P vs NP”答案的相对性

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

[7] 2023-07-18 15:37，[小结] “P对NP, P vs NP, P versus NP”问题的博文汇集

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

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

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

[9] 2011-09-15 17:50，A FULL PROOF to the P versus NP problem “P对NP（P versus NP, P vs NP）”问题的一个“完全证明”

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

[10] 2024-08-20 22:41，[笔记，逻辑，推理] 合情推理：猜测、实验、归纳、类比、联想、检测、……

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

感谢您的指教！

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

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