金屬所張志東研究員在解決鐵磁性三維伊辛模型精確解這個物理學(xué)難題后，又在計(jì)算機(jī)領(lǐng)域計(jì)算復(fù)雜性理論研究方面取得重要進(jìn)展。在近期的研究工作中，張志東研究員確定了自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度的下限，為一個絕對極小核模型的計(jì)算復(fù)雜度，它包含一個與其最近鄰平面相互作用的自旋玻璃二維伊辛模型，是亞指數(shù)時間，超多項(xiàng)式時間。論文發(fā)表在Journal of Materials Science and Technology 44 (2020) 116-120。 

玻璃是我們?nèi)粘Ｉ钪薪?jīng)常使用的用品，理解玻璃的形成機(jī)制以及動力學(xué)行為是一個重大科學(xué)問題。在磁性材料中，與玻璃相對應(yīng)，存在一種自旋玻璃的狀態(tài)。自旋玻璃是一個無序的磁體，其中原子的自旋不是按照規(guī)則圖案排列。與鐵磁體中的磁性有序相比較，自旋玻璃中的磁性無序，就類似于玻璃中的位置無序與石英的有序相比較。某種程度上，我們可以把自旋玻璃態(tài)看成具有自旋的無序取向的有序狀態(tài)，在其中自旋在空間無序地取向，但是可能隨時間的演化保持有序。非常有必要研究自旋玻璃體系的計(jì)算復(fù)雜性，它是物理、化學(xué)、生物、數(shù)學(xué)、材料科學(xué)以及計(jì)算機(jī)領(lǐng)域的重要課題?？梢杂靡列聊Ｐ蛠硌芯孔孕Ａ?。伊辛模型每個晶格點(diǎn)上有一個自旋，有自旋向上或者向下兩種狀態(tài)，自旋之間具有相互作用。伊辛模型不僅可以描述一個磁性晶格從順磁性到鐵磁性的相變，也可以描述不同的體系（如反鐵磁、格氣、大生物分子等）中有序-無序相變。本項(xiàng)工作關(guān)注一個具有隨機(jī)分布正和負(fù)的自旋相互作用以及存在阻挫的自旋玻璃三維伊辛模型（愛德華-安德森模型），僅考慮最近鄰自旋之間的相互作用?？梢酝ㄟ^計(jì)算體系所有2N個可能的狀態(tài)尋找具有N個格點(diǎn)的自旋玻璃伊辛模型的基態(tài)，所以計(jì)算復(fù)雜度的上限是O(2N)。自旋玻璃三維伊辛模型有拓?fù)湫?yīng)、隨機(jī)性、阻挫、非遍歷性質(zhì)等特征，導(dǎo)致其計(jì)算非常復(fù)雜，目前最好的算法獲得的結(jié)果是O(1.3N)，人們一直無法確定其計(jì)算復(fù)雜度的下限。 

張志東研究員證明了自旋玻璃三維伊辛模型（晶格點(diǎn)總數(shù)N=lmn）計(jì)算復(fù)雜度的四個定理： 

定理一，自旋玻璃三維伊辛模型的核心模型比一個絕對極小核心模型復(fù)雜得多，絕對極小核心模型包含一個自旋玻璃二維伊辛模型與其最近鄰平面相互作用。

定理二，自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度無法簡化為小于l乘以一個絕對極小核心模型的計(jì)算復(fù)雜度。  

定理三，自旋玻璃三維伊辛模型的絕對極小核心模型的計(jì)算復(fù)雜度無法被任何算法簡化為小于O(2mn)。它為O((1+)N)，遠(yuǎn)小于O(2N)，但是遠(yuǎn)大于并且無法簡化為多項(xiàng)式時間O(Np) 

定理四，自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度無法被任何算法簡化為小于O(2mn)。它是亞指數(shù)，但是超多項(xiàng)式的。 

本項(xiàng)工作確定了自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度的下限為亞指數(shù)時間，超多項(xiàng)式時間。自旋玻璃三維伊辛模型可以被映射為許多其他的科學(xué)問題，所以本項(xiàng)工作的結(jié)論可以直接推廣應(yīng)用，解決物理、化學(xué)、生物、數(shù)學(xué)、材料科學(xué)以及計(jì)算機(jī)領(lǐng)域一系列相關(guān)問題，特別是解決計(jì)算機(jī)領(lǐng)域的重大基礎(chǔ)科學(xué)問題。