我國科學家在復雜體系的計算復雜性的研究方面取得重要研究進展。中國科學院金屬研究所張志東研究員在計算機領域計算復雜性理論研究方面取得重要進展，確定了布爾可滿足性問題的計算復雜度下限。論文發(fā)表在Mathematics 11 (2023) 237。
隨著計算機領域的技術進步，人工智能正在影響我們?nèi)粘Ｉ畹姆椒矫婷?。而人工智能的進步依賴于計算算法的速度。如何在最短時間內(nèi)算出正確的解是計算機領域科學家最關心的問題。在計算機科學中，NP完全問題是非常重要的難題。這一類非平凡難題的共同特征是具有隨機性的模型系統(tǒng)中存在非平凡的拓撲結構、非平面性圖、非局域性或長程自旋糾纏。布爾可滿足性問題（縮寫為Satisfiability或SAT）是確定是否存在滿足給定布爾公式的解釋的問題。它詢問給定布爾公式的變量是否可以一致地用值“真”或“假”替換，公式計算結果為真。這種情況下的公式稱為可滿足。另一方面，如果不存在這樣的賦值，則對于所有可能的變量賦值，公式表示的函數(shù)為假，公式不可滿足。隨著布爾可滿足性問題的尺寸增加，問題的計算量增加。另外一方面，布爾可滿足性問題的計算復雜度也依賴于參量K的數(shù)值。布爾可滿足性問題屬于NP完全問題，非常有必要研究布爾可滿足性問題的計算復雜性。NP完全問題計算復雜度的上限為2的N次方，現(xiàn)在最好的算法是1.3的N次方。
張志東研究的出發(fā)點是另外一個NP完全問題 自旋玻璃三維伊辛模型（愛德華-安德森模型）。首先定義了自旋玻璃三維伊辛模型的絕對極小核心模型，它包含一個自旋玻璃二維伊辛模型與其最近鄰平面相互作用。證明使用近似或者打破絕對極小核心模型的自旋長程糾纏的任何算法都不能計算出自旋玻璃三維伊辛模型的精確解。根據(jù)自旋玻璃三維伊辛模型與自旋玻璃三維Z2格點規(guī)范模型的對偶關系以及相互作用的隨機性和阻錯，證明自旋玻璃三維伊辛模型可以被映射為K≥4的布爾可滿足性問題。然后證明，自旋玻璃三維伊辛模型的絕對極小核心模型可以被映射為K=3的布爾可滿足性問題。根據(jù)自旋玻璃三維伊辛模型的計算復雜度的下限是用蠻力搜素絕對極小核心模型的計算復雜度，證明K≥4的布爾可滿足性問題的計算復雜度的下限是用蠻力搜素K=3的布爾可滿足性問題的計算復雜度。張志東已經(jīng)在前期工作(J. Mater. Sci. Tech. 44 (2020) 116.)證明了尺寸為N=nml自旋玻璃三維伊辛模型的計算復雜度的下限是O(2nm)，是亞指數(shù)、超多項式的。所以，本項工作證明了K≥4的布爾可滿足性問題的計算復雜度的下限也是亞指數(shù)、超多項式的。本項工作通過物理思想做指導，分析體系的數(shù)學結構，提出一個判據(jù)，確定了NP完全問題的計算復雜度的下限為(1+無限小)的N次方。本項工作將會極大地優(yōu)化算法，從目前的1.3的N次方提升至(1+無限小)的N次方。
本項工作建立了布爾可滿足性問題與自旋玻璃三維伊辛模型的聯(lián)系，根據(jù)兩個問題的對偶關系確定了布爾可滿足性問題的計算復雜度的下限。布爾可滿足性問題可以被映射為許多其它的科學問題，所以本項工作的結論可以直接推廣應用，解決物理、化學、生物、數(shù)學、材料科學以及計算機領域一系列相關基礎科學問題。
論文鏈接：
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
自旋玻璃絕對極小模型中的三個相互作用與星形晶格的等價關系以及與三角晶格的對偶關系
