转发中国科学院金属研究所网页新闻：

我国科学家确定布尔可满足性问题计算复杂性下限

我国科学家在复杂体系的计算复杂性的研究方面取得重要研究进展。中国科学院金属研究所张志东研究员在计算机领域计算复杂性理论研究方面取得重要进展，确定了布尔可满足性问题的计算复杂度下限。论文发表在Mathematics 11 (2023) 237。

随着计算机领域的技术进步，人工智能正在影响我们日常生活的方方面面。而人工智能的进步依赖于计算算法的速度。如何在最短时间内算出正确的解是计算机领域科学家最关心的问题。在计算机科学中，NP完全问题是非常重要的难题。这一类非平凡难题的共同特征是具有随机性的模型系统中存在非平凡的拓扑结构、非平面性图、非局域性或长程自旋纠缠。布尔可满足性问题（缩写为Satisfiability或SAT）是确定是否存在满足给定布尔公式的解释的问题。它询问给定布尔公式的变量是否可以一致地用值“真”或“假”替换，公式计算结果为真。这种情况下的公式称为可满足。另一方面，如果不存在这样的赋值，则对于所有可能的变量赋值，公式表示的函数为假，公式不可满足。随着布尔可满足性问题的尺寸增加，问题的计算量增加。另外一方面，布尔可满足性问题的计算复杂度也依赖于参量K的数值。布尔可满足性问题属于NP完全问题，非常有必要研究布尔可满足性问题的计算复杂性。NP完全问题计算复杂度的上限为2的N次方，现在最好的算法是1.3的N次方。

张志东研究的出发点是另外一个NP完全问题;自旋玻璃三维伊辛模型（爱德华-安德森模型）。首先定义了自旋玻璃三维伊辛模型的绝对极小核心模型，它包含一个自旋玻璃二维伊辛模型与其最近邻平面相互作用。证明使用近似或者打破绝对极小核心模型的自旋长程纠缠的任何算法都不能计算出自旋玻璃三维伊辛模型的精确解。根据自旋玻璃三维伊辛模型与自旋玻璃三维Z₂格点规范模型的对偶关系以及相互作用的随机性和阻错，证明自旋玻璃三维伊辛模型可以被映射为K大于等于4的布尔可满足性问题。然后证明，自旋玻璃三维伊辛模型的绝对极小核心模型可以被映射为K=3的布尔可满足性问题。根据自旋玻璃三维伊辛模型的计算复杂度的下限是用蛮力搜索绝对极小核心模型的计算复杂度，证明K大于等于4的布尔可满足性问题的计算复杂度的下限是用蛮力搜索K=3的布尔可满足性问题的计算复杂度。张志东已经在前期工作(J. Mater. Sci. Tech. 44 (2020) 116.)证明了尺寸为N=nml自旋玻璃三维伊辛模型的计算复杂度的下限是O(2^nm)，是亚指数、超多项式的。所以，本项工作证明了K大于等于4的布尔可满足性问题的计算复杂度的下限也是亚指数、超多项式的。本项工作通过物理思想做指导，分析体系的数学结构，提出一个判据，确定了NP完全问题的计算复杂度的下限为(1+无限小)的N次方。本项工作将会极大地优化算法，从目前的1.3的N次方提升至(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