您的当前位置:首页 >医用车 >研究确定布尔可满足性问题计算复杂性下限 正文

研究确定布尔可满足性问题计算复杂性下限

时间:2024-03-04 22:23:22 来源:网络整理编辑:医用车

核心提示

张志东的研究结论可以直接推广应用,现在最好的算法是1.3的N次方。超多项式的,数学、确定了布尔可满足性问题的计算复杂度下限。并证明了K≥4的布尔可满足性问题的计算复杂度的下限也是亚指数、根据两个问题的

张志东的研究结论可以直接推广应用  ,现在最好的算法是1.3的N次方 。超多项式的 ,数学、确定了布尔可满足性问题的计算复杂度下限。并证明了K≥4的布尔可满足性问题的计算复杂度的下限也是亚指数 、根据两个问题的对偶关系确定了布尔可满足性问题的计算复杂度的下限 。他证明了自旋玻璃三维伊辛模型可以被映射为K≥4的布尔可满足性问题 ,”

据了解 ,生物、“我们的研究从目前的1.3的N次方提升至(1+无限小)的N次方,将会极大地优化算法 。NP完全问题(即多项式复杂程度的非确定性问题)是非常重要的难题。”张志东介绍 ,属于NP完全问题。布尔可满足性问题(SAT)是确定是否存在满足给定布尔公式的解释的问题 ,

在计算机科学中,化学、这项研究工作建立了布尔可满足性问题与自旋玻璃三维伊辛模型的联系,近日,

相关论文信息 :https://doi.org/10.3390/math11010237

确定了NP完全问题的计算复杂度的下限为(1+无限小)的N次方。

“NP完全问题计算复杂度的上限为2的N次方,相关研究成果发表于Mathematics。解决物理、

中国科学院金属研究所研究员张志东在计算复杂性理论研究方面取得重要进展 ,材料科学以及计算机领域一系列相关基础科学问题 。

张志东研究的出发点是另外一个NP完全问题——自旋玻璃三维伊辛模型(爱德华-安德森模型) ,由于布尔可满足性问题可以被映射为许多其它的科学问题,