- 我的订阅
- 教育
我们正处于一个信息大暴发的时代，每天都能产生数以百万计的新闻资讯！
虽然有大数据推荐，但面对海量数据，通过我们的调研发现，在一个小时的时间里，您通常无法真正有效地获取您感兴趣的资讯！
头条新闻资讯订阅，旨在帮助您收集感兴趣的资讯内容，并且在第一时间通知到您。可以有效节约您获取资讯的时间，避免错过一些关键信息。
确定布尔可满足性问题计算复杂度下限
本文转自：中国科学报
中国科学院金属研究所
确定布尔可满足性问题计算复杂度下限
本报讯（记者沈春蕾）中国科学院金属研究所研究员张志东在计算复杂性理论研究方面取得重要进展，确定了布尔可满足性问题的计算复杂度下限。近日，相关研究成果发表于《数学》。
在计算机科学中，NP完全问题（即多项式复杂程度的非确定性问题）是非常重要的难题。布尔可满足性问题属于NP完全问题。
张志东研究的出发点是另一个NP完全问题——自旋玻璃三维伊辛模型（爱德华-安德森模型），他证明了自旋玻璃三维伊辛模型可以被映射为K≥4的布尔可满足性问题，并证明了K≥4的布尔可满足性问题的计算复杂度的下限也是亚指数、超多项式的，确定了NP完全问题的计算复杂度的下限为（1+无限小）的N次方。
“NP完全问题计算复杂度的上限为2的N次方，现在最好的算法是1.3的N次方。”张志东介绍说，“我们的研究从目前的1.3的N次方提升至（1+无限小）的N次方，将会极大地优化算法。”
据了解，这项研究工作建立了布尔可满足性问题与自旋玻璃三维伊辛模型的联系，根据两个问题的对偶关系确定了布尔可满足性问题的计算复杂度下限。由于布尔可满足性问题可以被映射为许多其他的科学问题，该研究结论可以直接推广应用，解决物理、化学、生物、数学、材料科学以及计算机领域一系列相关基础科学问题。
相关论文信息：https://doi.org/10.3390/math11010237
以上内容为资讯信息快照，由td.fyun.cc爬虫进行采集并收录，本站未对信息做任何修改，信息内容不代表本站立场。
快照生成时间：2023-11-23 08:45:12
本站信息快照查询为非营利公共服务，如有侵权请联系我们进行删除。
信息原文地址：
