[重复就是力量] “P对NP, P vs NP, P versus NP”问题的情况汇报

术语 terminology

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

无穷： infinity

无穷公理： axiom of infinity

   下面简明地说明一下“P对N”的研究情况：已完成，已发表，待研究。

一、简史

   1993年暑假，发现了“P对NP”和“立体图”之间的关系。

   1993年秋冬，发现“NTM相当于DTM的幂集”。这是“P对NP”问题的核心。并且建立了 NPI 和连续统假设之间的对应或联系。

   由于“同行评议”的阻挠，一直到2010年，我一直找不到期刊正式发表。

   大约在2003年夏天，我见到一位大科学家。TA安慰我：

   “你不用着急发表。你现在全世界范围遥遥领先。其实这么说也不准确。

   实际上，我看只有你的结果是对的。

   其他人的研究结果，都有明显的缺陷。

   现在你是第一。我根本找不到谁是第二。……”

二、主要观点和后续工作

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

2.1  “P对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.

   已完成，已发表。《Transactions of Tianjin University》2011，《中国电子科学研究院学报》2011。

   通俗些：“P对NP”问题已经研究完毕。似乎不再需要进一步研究了。

2.2  后续工作

   它们是由“P对NP”的答案引出的新问题，不是P对NP”自身。

（1）事物的复杂性分层

   见《哲学研究》1999。已完成，已发表。

（2）人脑复杂性估计

   见《百科知识》1997。已完成，已发表。

（3）第二类数域

   见《中国电子科学研究院学报》2011。已完成，已发表。

   其进一步发展？我主要是没有精力，没有时间。待研究。

（4）集合论

   “ZFC公理集合论是万有理论，能够推导出经典数学的所有理论。但是，公理集合论无法被证明是一致的，人们只是在事实上迄今为止未在其中发现悖论（矛盾）；并且，其中的选择公理的地位一直为人所质疑。虽然数学仍未建立在严格的基础之上，但20世纪30、40年代后，大部分数学家已不再关心数学基础的问题。”

   因此，发展集合论，很可能牵一发而动全身。怕是不容易。待研究。

三、已公开发表的稿件汇总

3.1  发表的论文

[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

3.2  学术网站帖子

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

https://idea.cas.cn/viewdoc.action?docid=1275

3.2  《科学网》相关的博文

[1] 2023-12-01，《科学网》博克第 16 年开始！（俺在科学网开始第16年）

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

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

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

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

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

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

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

[5] 2023-07-11，[请教，讨论] P对NP（十）：一些相关的说明（研究思路、过渡参考资料等）

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

[6] 2023-07-10，[请教，讨论] P对NP（九）：请您看看，您还有哪些批评或疑问？

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

[7] 2023-07-09，[请教，讨论] P对NP（八）：“P对NP”为什么这么难？

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

[8] 2023-07-08，[请教，讨论] P对NP（七）：“形转换”与立体图、平面图

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

[9] 2023-07-07，[请教，讨论] P对NP（六）：无穷化版本与连续统假设CH

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

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

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

[11] 2023-07-04，[请教] P对NP（四）：相关要点小结（问答式）

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

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

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

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

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

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

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

[15] 2023-02-11，[随笔] “P对NP, P vs NP, P versus NP” Problem 问题：问题与求解方法

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

[16] 2023-01-18，[立此存照] 假如有人宣称证明了“P≠NP”，似乎只能证明他们不懂“什么是数学证明”

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

[17] 2023-01-17，[说明] 我对“P对NP”的所有研究，使用的都是现有的主流数学理论

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

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

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

[19] 2016-10-03，感谢“中国科学院科学智慧火花”：丘奇-图灵论题（Church-Turing Thesis），可能误导了 “P vs NP” 的研究

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

[20] 2016-09-27，平等的相对性与欺骗性（P vs NP）：卡片机傻拍2016（132）

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

[21] 2015-12-24，感谢“中国科学院科学智慧火花”：某些 NPI 可能是处在相变边界的 NPC

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

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

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

[23] 2012-03-23，[请教] P对NP：请***教授等专家指教（一） （一般背景知识汇报，无穷化版本下的“P对NP”）

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

[24] 2011-12-05，TTU论文《A non-canonical example to support that P is not equal to NP》已经刊出

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

[25] 2011-09-15，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

[26] 2011-09-06，My report and papers on "the P versus NP problem" (P vs NP)

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

[27] 2010-08-13，[请教]“P vs NP Problem”为什么这么困难？

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

[28] 2019-08-10，[求证] 1967年朗兰兹 Robert Phelan Langlands 写给韦伊的信里说

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

[29] 2019-11-14，[求助] 什么是发表？什么是当前国际科技界承认的发表？

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

附录：

附录一、当顶刊带头“不创新”时，学术网站开始引领人类科技进步

   大名鼎鼎的顶刊《Nature》在 2023-01-04 发表了“Papers and patents are becoming less disruptive over time 随着时间的推移，论文和专利的创新性越来越小”：

图2  Decline of disruptive science and technology.  颠覆性科学技术的衰落。

https://www.nature.com/articles/s41586-022-05543-x/figures/2  

https://www.nature.com/articles/s41586-022-05543-x

   a,b, Decline in CD5 over time, separately for papers (a, n = 24,659,076) and patents (b, n = 3,912,353). For papers, lines correspond to WoS research areas; from 1945 to 2010 the magnitude of decline ranges from 91.9% (social sciences) to 100% (physical sciences). For patents, lines correspond to National Bureau of Economic Research (NBER) technology categories; from 1980 to 2010 the magnitude of decline ranges from 93.5% (computers and communications) to 96.4% (drugs and medical). Shaded bands correspond to 95% confidence intervals. As we elaborate in the Methods, this pattern of decline is robust to adjustment for confounding from changes in publication, citation and authorship practices over time.

    a、 b，CD5随时间的下降，分别针对论文（a，n = 24,659,076）和专利（b，n = 3,912,353）。对于论文，行对应于WoS的研究领域；从1945年到2010年，下降幅度从91.9%（社会科学）到100%（物理科学）不等。对于专利，行对应于国家经济研究局（NBER）的技术类别；从1980年到2010年，下降幅度从93.5%（计算机和通信）到96.4%（药品和医疗）不等。阴影带对应于95%的置信区间。正如我们在方法中所阐述的，随着时间的推移，这种下降模式对出版物、引用和作者实践的变化所带来的混淆进行了强有力的调整。

图3  CD index of high-quality science over time.  随着时间的推移，高质量科学的CD索引。

https://www.nature.com/articles/s41586-022-05543-x/figures/5  

https://www.nature.com/articles/s41586-022-05543-x

   This figure shows changes in CD5 over time for papers published in Nature, Proceedings of the National Academy of Sciences (PNAS) and Science (inset plot, n = 223,745) and Nobel Prize-winning papers (main plot, n = 635), with several notable examples31,32,58,62,63,64,65,66 highlighted. Colours indicate the three different journals in the inset plot; colours indicate the three different fields in which the Nobel Prize is awarded in the main plot. Shaded bands correspond to 95% confidence intervals. For historical completeness, we plot CD index scores for all Nobel papers back to 1900 (the first year in which the prize was awarded); however, our main analyses begin in the post-1945 era, when the WoS data are generally more reliable. The figure indicates that changes in the quality of published science over time is unlikely to be responsible for the decline in disruption.

   该图显示了发表在《自然》、《美国国家科学院院刊》和《科学》上的论文CD5随时间的变化（插图，n = 223745）和诺贝尔奖获奖论文（主要情节，n = 635），突出显示了几个值得注意的示例31、32、58、62、63、64、65、66。颜色表示插图中的三种不同期刊；颜色表示主要情节中诺贝尔奖授予的三个不同领域。阴影带对应于95%的置信区间。为了历史的完整性，我们绘制了1900年（该奖项颁发的第一年）所有诺贝尔论文的CD索引分数；然而，我们的主要分析始于1945年后的时代，当时世界统计局的数据通常更可靠。该数字表明，随着时间的推移，已发表科学的质量变化不太可能是破坏性下降的原因。

   无需我多说了吧？

附录二、传统同行评审过程最常见的弊端是它消极对待真正的创新思想，拒绝领域内具革命性的文章

图4  《科学家》文章：论文同行评审过程有待改革，2010-08-06

https://news.sciencenet.cn/htmlnews/2010/8/235694.shtm

   Braben说，同行评审“会自动歧视那些挑战传统的意见，对大多数研究来说这没问题，但是对那些我们已知领域之外的新想法来说，同行评审可能对这些想法不利，而20世纪所有伟大的想法都是属于此类”。

https://news.sciencenet.cn/htmlnews/2008/12/214490.html

附录三、专家的个人感受

（1） William G. Kaelin Jr., 2017-05-23, Publish houses of brick, not mansions of straw

https://www.nature.com/news/publish-houses-of-brick-not-mansions-of-straw-1.22029

   The danger is that papers are increasingly like grand mansions of straw, rather than sturdy houses of brick.

   危险在于，论文越来越像稻草豪宅，而不是坚固的砖房。

图5  威廉·凯林（William G. Kaelin Jr），2019年诺贝尔医学奖得主

https://www.nobelprize.org/prizes/medicine/2019/kaelin/facts/

（2） 夏香根，2021-03-22，再论论文 精选

http://blog.sciencenet.cn/blog-3395313-1278147.html

   写不清楚的论文容易被接受，而写清楚的论文反而容易被拒稿。

   现在TSP里的论文错误率已经非常的高。有的论文的作者，跟着做的别人的论文还没有弄明白，就开始堆公式，写论文。别人的算法根本没理解，就改进别人的算法了，且还能在TSP上发表。尽管现在TSP比原来的TASSP多了至少十二倍的页数，但是有真正原创性的论文数量却远远不如八十年代的TASSP的多。当然，这是我个人的看法，一个跟踪此刊三十七年的老熟人的看法。

   自从要求交版面费后，学术论文已经完全变味了，发表论文再也代表不了科学研究。

图6  夏香根教授，Xiang-Gen Xia，Fellow of IEEE

https://sie.bit.edu.cn/szdw/jcrc/zjxz/

Fellow of IEEE

The Office of Naval Research Young Investigator Program (ONR YIP) Award

The National Science Foundation Faculty Early Career Development (NSF CAREER) Award

Xiang-Gen Xia, Charles Black Evans Professor, Electrical & Computer Engineering

https://www.ece.udel.edu/people/faculty/xianggen/

参考资料：

[1] 2023-08-22，数学基础/foundations of mathematics/何浩平，中国大百科全书，第三版网络版[DB/OL]

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

   ZFC公理集合论是万有理论，能够推导出经典数学的所有理论。但是，公理集合论无法被证明是一致的，人们只是在事实上迄今为止未在其中发现悖论（矛盾）；并且，其中的选择公理的地位一直为人所质疑。虽然数学仍未建立在严格的基础之上，但20世纪30、40年代后，大部分数学家已不再关心数学基础的问题。

相关链接：

[1] 2023-12-01，《科学网》博克第 16 年开始！（俺在科学网开始第16年）

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

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

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

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

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

感谢您的指教！

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

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