在解決鐵磁性三維伊辛模型精確解這個物理學難題后，中國科學院金屬研究所張志東研究員又在計算機領(lǐng)域計算復(fù)雜性理論研究方面取得重要進展。在近期的研究工作中，張志東研究員確定了自旋玻璃三維伊辛模型的計算復(fù)雜度的下限，為一個絕對極小核模型的計算復(fù)雜度，它包含一個與其最近鄰平面相互作用的自旋玻璃二維伊辛模型，是亞指數(shù)時間，超多項式時間。論文發(fā)表在《材料科學與技術(shù)》。

玻璃是人們?nèi)粘Ｉ钪薪?jīng)常使用的用品，理解玻璃的形成機制以及動力學行為是一個重大科學問題。在磁性材料中，與玻璃相對應(yīng)，存在一種自旋玻璃的狀態(tài)。自旋玻璃是一個無序的磁體，其中原子的自旋不是按照規(guī)則圖案排列。與鐵磁體中的磁性有序相比較，自旋玻璃中的磁性無序，就類似于玻璃中的位置無序與石英的有序相比較。某種程度上，可以把自旋玻璃態(tài)看成具有自旋的無序取向的有序狀態(tài)，在其中自旋在空間無序地取向，但是可能隨時間的演化保持有序。

研究自旋玻璃體系的計算復(fù)雜性，是物理、化學、生物、數(shù)學、材料科學以及計算機領(lǐng)域的重要課題。在用伊辛模型來研究自旋玻璃中，伊辛模型每個晶格點上有一個自旋，有自旋向上或者向下兩種狀態(tài)，自旋之間具有相互作用。伊辛模型不僅可以描述一個磁性晶格從順磁性到鐵磁性的相變，也可以描述不同的體系（如反鐵磁、格氣、大生物分子等）中有序-無序相變。該研究關(guān)注了一個具有隨機分布正和負的自旋相互作用以及存在阻挫的自旋玻璃三維伊辛模型（愛德華-安德森模型），僅考慮最近鄰自旋之間的相互作用?？梢酝ㄟ^計算體系所有2^N個可能的狀態(tài)尋找具有N個格點的自旋玻璃伊辛模型的基態(tài)，所以計算復(fù)雜度的上限是O(2^N)。自旋玻璃三維伊辛模型有拓撲效應(yīng)、隨機性、阻挫、非遍歷性質(zhì)等特征，導(dǎo)致其計算非常復(fù)雜，目前最好的算法獲得的結(jié)果是O(1.3^N)，人們一直無法確定其計算復(fù)雜度的下限。

張志東研究員證明了自旋玻璃三維伊辛模型（晶格點總數(shù)N=lmn）計算復(fù)雜度的四個定理，確定了自旋玻璃三維伊辛模型的計算復(fù)雜度的下限為亞指數(shù)時間，超多項式時間。自旋玻璃三維伊辛模型可以被映射為許多其他的科學問題，可以直接推廣應(yīng)用以解決物理、化學、生物、數(shù)學、材料科學以及計算機領(lǐng)域一系列相關(guān)問題，特別是解決計算機領(lǐng)域的重大基礎(chǔ)科學問題。