||
我的前期工作解决自旋玻璃三维伊辛模型和布尔可满足性问题的计算复杂度问题,2020年和2023年先后在JMST和Mathematics上发表两篇论文。2024年5月23日我在科学网上发表博文《原创工作发表难之上听待和》。提出,如果能够满足以下三个条件之一:JMST和Mathematics两篇论文的引用之和达到100次;两篇论文引用的独立研究组数目之和达到25个;在SCI刊物发表出第三篇相关课题的论文。当时大呆预言:慢则两三年,快则一年,最快在2024年底,就可以在科学网上公开谜底!
目前JMST和Mathematics两篇论文的引用之和达到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人。所以,大呆的胆子壮了些。再加上,非常巧合,2025年5月22日第三篇相关论文(背包问题的计算复杂度)在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
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2025-6-25 13:59
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社