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

博文

原创工作发表难之步步为营 精选

已有 6394 次阅读 2023-3-20 08:38 |个人分类:追梦|系统分类:科研笔记

 

    我在科学网上先后发表了几篇博文,论述原创工作发表难,包括《原创工作发表难之叶公好龙》、《原创工作发表难之慧眼识珠》和《原创工作发表难之断尾求生》。断尾求生之后的最佳策略,大呆认为是步步为营。因为要让同行一下子就理解原创工作的思想和意义是非常困难的,需要有足够的耐心,采取步步为营,切香肠的办法,逐步对学术界进行渗透,才能实现最后的目标。

        我在《原创工作发表难之断尾求生》介绍了自旋玻璃三维伊辛模型的计算复杂度的工作。这是一个计算机领域的重要课题。为了能够发表保护优先权,我断尾求生,将与计算机领域相关的内容全部删去,2020年发表在材料领域的刊物JMST。又步步为营,经过3年的努力,将与计算机相关问题的内容发表在数学刊物。下面简要地介绍这个工作的内容:

在计算机科学中,NP完全问题是非常重要的难题。这一类非平凡难题的共同特征是具有随机性的模型系统中存在非平凡的拓扑结构、非平面性图、非局域性或长程自旋纠缠。布尔可满足性问题(缩写为SatisfiabilitySAT)是确定是否存在满足给定布尔公式的解释的问题。它询问给定布尔公式的变量是否可以一致地用值替换,公式计算结果为真。这种情况下的公式称为可满足。另一方面,如果不存在这样的赋值,则对于所有可能的变量赋值,公式表示的函数为假,公式不可满足。随着布尔可满足性问题的尺寸增加,问题的计算量增加。另外一方面,布尔可满足性问题的计算复杂度也依赖于参量K的数值。K大于等于3的布尔可满足性问题属于NP完全问题,非常有必要研究布尔可满足性问题的计算复杂性。计算复杂度的上限为2的N次方,现在最好的算法是1.3的N次方。

本项研究的出发点是另外一个NP完全问题,自旋玻璃三维伊辛模型(爱德华-安德森模型)。首先定义了自旋玻璃三维伊辛模型的绝对极小核心模型,它包含一个自旋玻璃二维伊辛模型与其最近邻平面相互作用。证明使用近似或者打破绝对极小核心模型的自旋长程纠缠的任何算法都不能计算出自旋玻璃三维伊辛模型的精确解。根据自旋玻璃三维伊辛模型与自旋玻璃三维Z2格点规范模型的对偶关系以及相互作用的随机性和阻错,证明自旋玻璃三维伊辛模型可以被映射为K>=4的布尔可满足性问题。然后证明,自旋玻璃三维伊辛模型的绝对极小核心模型可以被映射为K=3的布尔可满足性问题。根据自旋玻璃三维伊辛模型的计算复杂度的下限是用蛮力搜素绝对极小核心模型的计算复杂度,证明K>=4的布尔可满足性问题计算复杂度的下限是用蛮力搜素K=3的布尔可满足性问题计算复杂度。由于我已经在前期工作证明了自旋玻璃三维伊辛模型的计算复杂度的下限是亚指数、超多项式的,所以,本项工作证明了K>=4的布尔可满足性问题计算复杂度的下限也是亚指数、超多项式的。我是通过物理思想做指导,分析体系的数学结构,提出一个判据,确定了NP完全问题的计算复杂度的下限为(1+无限小)的N次方。

本项工作建立了布尔可满足性问题与自旋玻璃三维伊辛模型的联系,根据两个问题的对偶关系确定了布尔可满足性问题计算复杂度的下限。布尔可满足性问题可以被映射为许多其它的科学问题,所以项工作的结论可以直接推广应用,解决物理、化学、生物、数学、材料科学以及计算机领域一系列相关基础科学问题。

论文链接:

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

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



https://blog.sciencenet.cn/blog-2344-1381081.html

上一篇:无招胜有招之北冥篇
下一篇:我的两个学术报告
收藏 IP: 59.152.39.*| 热度|

23 武夷山 王涛 崔锦华 郑永军 檀成龙 李世春 代恒伟 梁洪泽 宁利中 杨正瓴 高友鹤 辜英求 王安良 周忠浩 田云川 褚海亮 叶建军 孙颉 汪凯 李学宽 黄河宁 郑强 胡泽春

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

数据加载中...

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

GMT+8, 2024-4-13 09:08

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部