中国科学院金属研究所研究员张志东在计算机领域计算复杂性理论研究方面取得进展。研究中，确定了自旋玻璃三维伊辛模型的计算复杂度的下限，为一个绝对极小核模型的计算复杂度，它包含一个与其最近邻平面相互作用的自旋玻璃二维伊辛模型，是亚指数时间，超多项式时间。相关研究成果发表在Journal of Materials Science and Technology上。

　　玻璃是常见用品，理解玻璃的形成机制及动力学行为是重要的科学问题。在磁性材料中，与玻璃相对应，存在一种自旋玻璃的状态。自旋玻璃是一个无序的磁体，其中原子的自旋不是按照规则图案排列。与铁磁体中的磁性有序相比较，自旋玻璃中的磁性无序，类似于玻璃中的位置无序与石英的有序相比较。某种程度上，可以把自旋玻璃态看成具有自旋的无序取向的有序状态，在其中自旋在空间无序地取向，但可能随时间的演化保持有序。研究自旋玻璃体系的计算复杂性十分必要，它是物理、化学、生物、数学、材料科学以及计算机领域的重要课题。可以用伊辛模型来研究自旋玻璃，伊辛模型每个晶格点上有一个自旋，有自旋向上或者向下两种状态，自旋之间具有相互作用。伊辛模型可以描述一个磁性晶格从顺磁性到铁磁性的相变，也可以描述不同的体系（如反铁磁、格气、大生物分子等）中有序-无序相变。该研究关注一个具有随机分布正和负的自旋相互作用以及存在阻挫的自旋玻璃三维伊辛模型（爱德华-安德森模型），仅考虑最近邻自旋之间的相互作用。可以通过计算体系所有2^N个可能的状态寻找具有N个格点的自旋玻璃伊辛模型的基态，所以计算复杂度的上限是O(2^N)。自旋玻璃三维伊辛模型有拓扑效应、随机性、阻挫、非遍历性质等特征，导致其计算复杂，目前算法获得的结果是O(1.3^N)，无法确定其计算复杂度的下限。

　　该研究证明了自旋玻璃三维伊辛模型（晶格点总数N=lmn）计算复杂度的四个定理：定理一，自旋玻璃三维伊辛模型的核心模型比一个绝对极小核心模型复杂得多，绝对极小核心模型包含一个自旋玻璃二维伊辛模型与其最近邻平面相互作用。定理二，自旋玻璃三维伊辛模型的计算复杂度无法简化为小于l乘以一个绝对极小核心模型的计算复杂度。定理三，自旋玻璃三维伊辛模型的绝对极小核心模型的计算复杂度无法被任何算法简化为小于O(2^mn)。它为O((1+)^N)，远小于O(2^N)，但是远大于并且无法简化为多项式时间O(N^p)。定理四，自旋玻璃三维伊辛模型的计算复杂度无法被任何算法简化为小于O(2^mn)。它是亚指数，但是超多项式的。

　　研究确定了自旋玻璃三维伊辛模型的计算复杂度的下限为亚指数时间，超多项式时间。自旋玻璃三维伊辛模型可以被映射为许多其他科学问题，研究结论可以直接推广应用，解决物理、化学、生物、数学、材料科学以及计算机领域的相关问题，特别是解决计算机领域的基础科学问题。