[请教，往日] 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

图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

相关链接：

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

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

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

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

[3] 2024-06-04 22:37，[往日（19）, P vs NP]：从互容、排序、矩阵乘法、定性推理，到 P vs NP

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

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

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

[5] 2024-03-23 19:58，[P vs NP，讨论，交作业] 郑波尽老师：P vs NP 的本质，及其研究方法

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

[6] 2023-07-31 18:21，[小汇报] 对我有“冲击力”的几本书（科普、专著）（1）：“P对NP”问题、“反思经典电磁理论”

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

[7] 2023-07-19 16:07，[新术语] 宇宙“均寂”（均匀地寂灭）与“幂集公理”

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

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

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

[9] 中国科学院科学智慧火花，杨正瓴，2024-11-19 06:54，新术语“均寂”：对“热寂”的进一步推广

https://idea.cas.cn/zhhh/sxwlhxytw/sx/info/2024/551462.html

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

[10] 2022-07-01 15:34，往日（13）：我命名了 7 个无穷基数

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

[11] 2022-07-28 14:41，往日（15）：2009-11-13 对21世纪数学发展的看法

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

[12] 2022-06-30 14:26，往日（12）：数学里“无穷小 infinitesimal”的新符号建议

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

感谢您的指教！

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

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