我心如伊分享 http://blog.sciencenet.cn/u/张志东 在一个浮躁的社会和纷杂的年代,在心灵深处保持一片宁静的时空。

博文

原创工作发表难之自摸和牌

已有 788 次阅读 2025-6-2 08:35 |个人分类:追梦|系统分类:科研笔记

     我的前期工作解决自旋玻璃三维伊辛模型和布尔可满足性问题的计算复杂度问题,2020年和2023年先后在JMSTMathematics上发表两篇论文。2024523日我在科学网上发表博文《原创工作发表难之上听待和》。提出,如果能够满足以下三个条件之一:JMSTMathematics两篇论文的引用之和达到100次;两篇论文引用的独立研究组数目之和达到25个;在SCI刊物发表出第三篇相关课题的论文。当时大呆预言:慢则两三年,快则一年,最快在2024年底,就可以在科学网上公开谜底!

目前JMSTMathematics两篇论文的引用之和达到67次;两篇论文引用的独立研究组数目之和达到15个。没有达到预设的标准。尽管如此,其中一些计算机领域的同行引用还是非常正面的。例如:

H.J. Xu, S. Dasgupta, A. Pothen, A. Banerjee, Dynamic asset allocation with expected shortfall via quantum annealing, Entropy, 25 (2023) 541. 在论文的第6页指出我确定了具有晶格尺寸N = lmn自旋玻璃三维伊辛模型的复杂度为O(2mn)And in the case of spin-glass three dimensional Ising model with lattice size of N = lmn, the complexity is O(2mn) [34], which is NP-Hard as well.

F.X. Liu, L.-M. Duan, Computational characteristics of the random-field Ising model with long-range interaction, Phys. Rev. A 108, (2023) 012415. 在前言部分明确指出我验证了三维伊辛模型的计算复杂度下限:The authors of Ref. [13] gave a further examination of the lower bound of the complexity of the three-dimensional (3D) Ising model with magnetic field.

S. Nagy, R. Paredes, J.M. Dudek, L. Dueñas-Osorio, M.Y. Vardi, Ising model partition-function computation as a weighted counting problem, Phys. Rev. E 109 (2024) 055301. 2页认可我关于布尔可满足性的拓扑和复杂度与伊辛模型拓扑的关系:Critical topological and hardness insights in SAT can be related to topological features of Ising models [30],

A.A. Gangat and J. Gray, Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices, Phys. Rev. E 110 (2024) 065306. 在第7页认可我布尔可满足性与三维伊辛自旋玻璃的映射以及非局域效应的分析:(see also Ref. [54] regarding mapping between K-SAT and the cubic-lattice classical Ising spin glass).When dealing with such square- and cubic-lattice spin glasses that encode more general spin glasses whose interaction graphs are highly nonlocal, it is likely that themethod investigated here would suffer from a significant bias in the sampling due to the finite bond dimension (the nonlocal nature of the original model encode into the lattice model would likely require very large bond dimension for the present method to sample the lattice model approximately fairly).

感兴趣的网友可以详细阅读引文。

另外,正面引用的论文作者总数、论文的审稿人总数、通过emails私人通信表达支持和祝贺的同行人数之和已经远超100人。所以,大呆的胆子壮了些。再加上,非常巧合,2025522第三篇相关论文(背包问题的计算复杂度)在SCI刊物AIMS Mathematics发表,满足了上面的第三条。大呆兑现诺言,在科学网上公开谜底:我的工作就是确定了NP完全问题的计算复杂度下限。

NP完全问题是计算机科学中非常重要的难题。计算复杂性理论中,NP表示非确定性多项式时间,NP问题定义为在一个非确定性图灵机上以多项式时间求解的决定性问题的集合。P问题是在确定性图灵机上以多项式时间求解的问题的集合。在NP中,以多项式时间确认解的决定性问题的集合归类为NP完全问题。在NP中所有其他问题都可以在多项式时间内约化为NP完全问题(以及其特例)。NP完全问题的共同特征是具有随机性的模型系统中存在非平拓扑结构、非平面性图、非局域性或长程自旋纠缠。

AIMS Mathematics论文中,大呆首先分析了NP完全问题中非平拓扑结构的起源。从自旋玻璃三维伊辛模型出发,详细地阐明三维晶格上自旋排列与统计物理中转移矩阵的二维特征之间的矛盾导致非平拓扑结构。确认自旋玻璃三维伊辛模型存在绝对极小核心(AMC)模型。用蛮力搜索绝对极小核心模型决定了其计算复杂度的下限。并且,确认自旋玻璃三维伊辛模型中存在NP中间问题,给出体系的计算复杂度的相图。绝对极小核心模型存在于NP完全问题和NP中间问题的边界上。进一步地,根据自旋玻璃三维伊辛模型和背包问题之间的映射,证明背包问题同样存在绝对极小核心模型和NP中间问题,也给出背包问题的计算复杂度相图。并且证明了背包问题计算复杂度的下限是亚指数、超多项式的。

总结:大呆严格地证明了NP不等于P,从而解决了NP完全问题。

论文链接:

1.自旋玻璃三维伊辛模型计算复杂度: Z.D. Zhang, J. Mater. Sci. Tech. 44 (2020) 116-120.  https://doi.org/10.1016/j.jmst.2019.12.009 

2.布尔可满足性问题计算复杂度,Z.D. Zhang, Mathematics, 11 (2023) 237. https://doi.org/10.3390/math11010237

    3.背包问题计算复杂度,Z.D. Zhang, AIMS Mathematics 10 (2025) 11918-11938. https://www.aimspress.com/article/doi/10.3934/math.2025538



https://wap.sciencenet.cn/blog-2344-1488153.html

上一篇:AI科普背包问题新进展
收藏 IP: 210.72.130.*| 热度|

21 许培扬 王涛 崔锦华 尤明庆 郑永军 刘进平 杨正瓴 宁利中 钱大鹏 雒运强 朱林 钟炳 檀成龙 李学宽 高友鹤 孙颉 褚海亮 武夷山 赵凤光 池德龙 逄焕东

该博文允许注册用户评论 请点击登录 评论 (16 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2025-6-5 00:55

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部