金屬所張志東研究員在解決鐵磁性三維伊辛模型精確解這個(gè)物理學(xué)難題后，又在計(jì)算機(jī)領(lǐng)域計(jì)算復(fù)雜性理論研究方面取得重要進(jìn)展。在近期的研究工作中，張志東研究員確定了自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度的下限，為一個(gè)絕對(duì)極小核模型的計(jì)算復(fù)雜度，它包含一個(gè)與其最近鄰平面相互作用的自旋玻璃二維伊辛模型，是亞指數(shù)時(shí)間，超多項(xiàng)式時(shí)間。論文發(fā)表在Journal of Materials Science and Technology 44 (2020) 116-120。
玻璃是我們?nèi)粘Ｉ钪薪?jīng)常使用的用品，理解玻璃的形成機(jī)制以及動(dòng)力學(xué)行為是一個(gè)重大科學(xué)問題。在磁性材料中，與玻璃相對(duì)應(yīng)，存在一種自旋玻璃的狀態(tài)。自旋玻璃是一個(gè)無序的磁體，其中原子的自旋不是按照規(guī)則圖案排列。與鐵磁體中的磁性有序相比較，自旋玻璃中的磁性無序，就類似于玻璃中的位置無序與石英的有序相比較。某種程度上，我們可以把自旋玻璃態(tài)看成具有自旋的無序取向的有序狀態(tài)，在其中自旋在空間無序地取向，但是可能隨時(shí)間的演化保持有序。非常有必要研究自旋玻璃體系的計(jì)算復(fù)雜性，它是物理、化學(xué)、生物、數(shù)學(xué)、材料科學(xué)以及計(jì)算機(jī)領(lǐng)域的重要課題?？梢杂靡列聊Ｐ蛠硌芯孔孕Ａ?。伊辛模型每個(gè)晶格點(diǎn)上有一個(gè)自旋，有自旋向上或者向下兩種狀態(tài)，自旋之間具有相互作用。伊辛模型不僅可以描述一個(gè)磁性晶格從順磁性到鐵磁性的相變，也可以描述不同的體系（如反鐵磁、格氣、大生物分子等）中有序-無序相變。本項(xiàng)工作關(guān)注一個(gè)具有隨機(jī)分布正和負(fù)的自旋相互作用以及存在阻挫的自旋玻璃三維伊辛模型（愛德華-安德森模型），僅考慮最近鄰自旋之間的相互作用?？梢酝ㄟ^計(jì)算體系所有2N個(gè)可能的狀態(tài)尋找具有N個(gè)格點(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ù)雜度的四個(gè)定理：
定理一，自旋玻璃三維伊辛模型的核心模型比一個(gè)絕對(duì)極小核心模型復(fù)雜得多，絕對(duì)極小核心模型包含一個(gè)自旋玻璃二維伊辛模型與其最近鄰平面相互作用。
定理二，自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度無法簡(jiǎn)化為小于l乘以一個(gè)絕對(duì)極小核心模型的計(jì)算復(fù)雜度。
定理三，自旋玻璃三維伊辛模型的絕對(duì)極小核心模型的計(jì)算復(fù)雜度無法被任何算法簡(jiǎn)化為小于O(2mn)。它為O((1+ )N)，遠(yuǎn)小于O(2N)，但是遠(yuǎn)大于并且無法簡(jiǎn)化為多項(xiàng)式時(shí)間O(Np)
定理四，自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度無法被任何算法簡(jiǎn)化為小于O(2mn)。它是亞指數(shù)，但是超多項(xiàng)式的。
本項(xiàng)工作確定了自旋玻璃三維伊辛模型的計(jì)算復(fù)雜度的下限為亞指數(shù)時(shí)間，超多項(xiàng)式時(shí)間。自旋玻璃三維伊辛模型可以被映射為許多其他的科學(xué)問題，所以本項(xiàng)工作的結(jié)論可以直接推廣應(yīng)用，解決物理、化學(xué)、生物、數(shù)學(xué)、材料科學(xué)以及計(jì)算機(jī)領(lǐng)域一系列相關(guān)問題，特別是解決計(jì)算機(jī)領(lǐng)域的重大基礎(chǔ)科學(xué)問題。
