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