金属所确定布尔可满足性问题计算复杂性下限
中国科学院金属研究所研究员张志东在计算机领域计算复杂性理论研究方面取得重要进展，确定了布尔可满足性问题的计算复杂度下限。相关研究成果发表在《数学》（Mathematics）上。
随着计算机领域的技术进步，人工智能正在影响着日常生活。人工智能的进步依赖于计算算法的速度。如何在最短时间内算出正确的解，是计算机领域的关键问题。在计算机科学中，NP完全问题是重要的难题。这一类非平凡难题的共同特征是具有随机性的模型系统存在非平凡的拓扑结构、非平面性图、非局域性或长程自旋纠缠。布尔可满足性问题（缩写为Satisfiability或SAT）是确定是否存在满足给定布尔公式的解释的问题。它询问给定布尔公式的变量是否可以一致地用值“真”或“假”替换，公式计算结果为真。这种情况下的公式称为可满足。如果不存在这样的赋值，则对于所有可能的变量赋值，公式表示的函数为假，公式不可满足。随着布尔可满足性问题的尺寸增加，问题的计算量增加。此外，布尔可满足性问题的计算复杂度依赖参量K的数值。布尔可满足性问题属于NP完全问题，因而有必要研究布尔可满足性问题的计算复杂性。NP完全问题计算复杂度的上限为2的N次方，现在最好的算法是1.3的N次方。
本研究的出发点是另一个NP完全问题——自旋玻璃三维伊辛模型（爱德华-安德森模型）。该研究定义了自旋玻璃三维伊辛模型的绝对极小核心模型。它包含一个自旋玻璃二维伊辛模型与其最近邻平面相互作用。研究表明，使用近似或者打破绝对极小核心模型的自旋长程纠缠的任何算法，均不能计算出自旋玻璃三维伊辛模型的精确解。根据自旋玻璃三维伊辛模型与自旋玻璃三维Z2格点规范模型的对偶关系，以及相互作用的随机性和阻错，该研究证明自旋玻璃三维伊辛模型可以被映射为K≥4的布尔可满足性问题。进一步，研究表明，自旋玻璃三维伊辛模型的绝对极小核心模型可以被映射为K=3的布尔可满足性问题。根据自旋玻璃三维伊辛模型的计算复杂度的下限是用蛮力搜素绝对极小核心模型的计算复杂度，研究显示，K≥4的布尔可满足性问题的计算复杂度的下限是用蛮力搜素K=3的布尔可满足性问题的计算复杂度。前期成果证明了尺寸为N=nml自旋玻璃三维伊辛模型的计算复杂度的下限是O(2nm)，是亚指数、超多项式的。因此，本工作证明了K≥4的布尔可满足性问题的计算复杂度的下限也是亚指数、超多项式的。本工作通过物理思想做指导，分析体系的数学结构，提出一个判据，确定了NP完全问题的计算复杂度的下限为（1+无限小）的N次方。上述成果将优化算法即从目前的1.3的N次方提升至（1+无限小）的N次方。
本工作建立了布尔可满足性问题与自旋玻璃三维伊辛模型的联系，并根据两个问题的对偶关系确定了布尔可满足性问题的计算复杂度的下限。布尔可满足性问题可以被映射为其他的科学问题，故本工作的结论可以直接推广应用，有望解决物理、化学、生物、数学、材料科学及计算机领域的相关基础科学问题。
消息来源：中国科学院官网
