科学网-[请教，往日] P对NP（二）：思考 P vs NP 的几个关键事件点-杨正瓴的博文

切换到桌面版

[请教，往日] P对NP（二）：思考 P vs NP 的几个关键事件点

2025-4-27 22:32

阅读：661

[请教，往日] P对NP（二）：思考 P vs NP 的几个关键事件点

下面列出的时间，不一定很准确。但应该差不多。

（1）1993夏天

“大多数指数时间算法只是穷举搜索法的变种, 而多项式时间算法通常只有在对问题的结构有了某些比较深入的了解之后才能给出。”

（2）1993夏天

2SAT 是 P，3SAT 是 NPC (NP-Complete)。

对照：有“指数界 n!候选解”的“排序 sorting”问题，为什么是P？

（3）1993夏天、秋天

NTM，相当于 TM 的幂集：

主要是“转移函数 transition function”的差别。

ZPC，以及 NPI (NP-Intermediate) 在无穷化后，对应 CH (continuum hypothesis)。

（4）2011-08 前后

P vs NP：真的存在“概率化”的版本！

尚未公开发表。

（5）2023-07-19 前后

从“热寂 heat death”到“均寂”：数学基础里“策梅洛-弗兰克尔集合论，Zermelo-Fraenkel set theory, ZFC”里“幂集公理 axiom of power set”的合理性。

参考资料：

[1] Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W. H. Freeman, 1979

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

1979 Computers and intractability (Michael R. Garey David S. Johnson).jpg

图1 Computers and intractability: A guide to the theory of NP-completeness (A Series of books in the mathematical sciences), 1979-01-01

https://m.media-amazon.com/images/I/A1sD5q2oksL._SL1500_.jpg

https://www.amazon.com/Computers-intractability-NP-completeness-mathematical-sciences/dp/0716710447

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

https://bkimg.cdn.bcebos.com/pic/810a19d8bc3eb13533fa55041857bfd3fd1f4134ee70

https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%92%8C%E9%9A%BE%E8%A7%A3%E6%80%A7%20:%20NP%E5%AE%8C%E5%85%A8%E6%80%A7%E7%90%86%E8%AE%BA%E5%AF%BC%E5%BC%95?fromModule=lemma_search-box

已经发表的论文等：

[1] 1995年10月之前，我还写过一篇论文参加了“挑战杯”比赛。不过我没有任何材料可以证明这个。

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

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

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

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

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

doi: 10.3969/j.issn.1673-5692.2008.06.002

https://d.wanfangdata.com.cn/periodical/Ch9QZXJpb2RpY2FsQ0hJTmV3UzIwMjUwMTE2MTYzNjE0EhFkemt4anNwbDIwMDgwNjAwMhoIMTI1MW95ZG0%3D

https://www.cqvip.com/doc/journal/965772631?sign=0695dbf10c7f251312e6b93709c7619810be4b95515d58cec495b11fc1a6fe71&expireTime=1744321759348&resourceId=965772631

https://kns.cnki.net/kcms2/article/abstract?v=_dzes7vZToNVoPowmQw1gARVMfmQJCdq0clFD1JTfcrHse_BDMYF0yHSj3byjEqD6KVYWT_UcsmeHJuKaa2QaqaX1wVwrV0qkvVoDZZZpkyiedcs7nAtDt5u2PVym21ya8X164JT-oTQSDCyfKKIRyBpGU5jQ58vFb0Vga06quIl6mRrF18mVw==&uniplatform=NZKPT&language=CHS

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

doi: 10.3969/j.issn.1673-5692.2011.04.009

https://d.wanfangdata.com.cn/periodical/Ch9QZXJpb2RpY2FsQ0hJTmV3UzIwMjUwMTE2MTYzNjE0EhFkemt4anNwbDIwMTEwNDAwORoIaWFnbnR5dDU%3D

https://www.cqvip.com/doc/journal/955236059?sign=30e3a846a9f5cce0aa9328fb10ae2ef236a390a85f609490178b876ac810c6b1&expireTime=1744321539659&resourceId=955236059

https://kns.cnki.net/kcms2/article/abstract?v=_dzes7vZToOaJyR7v744ry0H4PSZF-8tV_7FKh-WDhizTtBvUWUfqQMmn84g_zByyxRn4o4reoKcMRtlFcsH-w629GsqeKHRRSJu0Xxrc2mHtmdTfj5wEGyOIMhtJXgRREzpwU5wAexouFmRFWqGg49HLhpxq-ZAGaRYm8s1WWBx3M5wPZmLzg==&uniplatform=NZKPT&language=CHS

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

doi: 10.1007/s12209-011-1593-5

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

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

https://lib.cqvip.com/Qikan/Article/Detail?id=40032670&from=Qikan_Search_Index