近日，中国科学院金属研究所研究员张志东确定了“背包问题”的计算复杂度下限，在该领域取得理论进展。
“背包问题”是计算机科学中经典的NP完全问题（非确定性图灵机多项式复杂度求解的决定问题）。“背包问题”的目标是，在限制所有物体权重之和小于或等于最大权重的前提下，最大化所有物体的价值之和。“背包问题”可用来进行组合数学、密码学、商业等领域的计算，还可以应用在不同领域的决策，如寻找减少原材料使用、投资组合的选择、密钥产生等最优化搜寻路径。
“背包问题”与自旋玻璃模型的联系是，“背包问题”的二元决定性变量对应于自旋向上和自旋向下两种状态。“背包问题”的权重对应于自旋之间的相互作用。“背包问题”的哈密顿量可以映射成具有偏置场的自旋玻璃模型的哈密顿。因此，通过求解自旋玻璃模型可以求解“背包问题”。在“背包问题”中最大化所有物体的价值之和等价于在自旋玻璃模型中最小化自由能。
该研究分析了NP完全问题中非平庸拓扑结构的起源。研究从自旋玻璃三维伊辛模型出发，阐明三维晶格上自旋排列与统计物理中转移矩阵的二维特征之间的矛盾导致非平庸拓扑结构。研究确认，自旋玻璃三维伊辛模型存在绝对极小核心模型，为一层晶格自旋玻璃伊辛模型与其最近邻层自旋的相互作用。它等于两层晶格自旋玻璃三维伊辛模型减去一个自旋玻璃二维伊辛模型。研究发现，用蛮力搜索绝对极小核心模型决定其计算复杂度的下限。同时，研究发现自旋玻璃三维伊辛模型存在NP中间问题，给出体系的计算复杂度的相图。绝对极小核心模型存在于NP完全问题和NP中间问题的边界上。进一步，研究根据自旋玻璃三维伊辛模型和“背包问题”之间的映射，证明“背包问题”同样存在绝对极小核心模型和NP中间问题，给出“背包问题”的计算复杂度相图，并证明“背包问题”的计算复杂度的下限是亚指数、超多项式的。
该研究以物理思想为指导，分析体系的数学结构，提出一个判据，确定了NP完全问题的计算复杂度的下限为（1+无限小）的N次方。同时，这一成果为NP完全问题的数值计算提供了指导性思维。
上述研究建立了“背包问题”与自旋玻璃三维伊辛模型的联系，并根据两个问题的关系确定了“背包问题”的计算复杂度的下限。同时，该工作得出的结论有望直接推广应用，来解决计算机、物理、化学、生物、数学和材料科学领域相关的基础科学问题。
相关研究成果发表在《AIMS数学》（AIMS Mathematics）上。
论文链接
自旋玻璃三维伊辛模型最小核模型示意图
交变磁性是近年来提出的第三类基本磁相。交变磁性既有反铁磁体的零净磁场，又具有铁磁体的自旋劈裂现象。通常，两者被认为是不相容的。交变磁性兼具铁磁性和反铁磁性的优势，为制造自旋电子器件带来了新突破口，在磁存 学龄前时期是儿童身心发展的重要阶段，学前教育是国民教育体系的重要组成部分。习近平总书记强调：“要加强对基础教育的支持力度，办好学前教育。”为实现“幼有所育”，规范和促进学前教育发展，满足 中国教育报-中国教育新闻网讯（记者 黄星）日前，福建省福州市委教育工委书记、市教育局党组书记、局长游昕一行赴闽侯第一中学开展食品安全专项督导工作，并在学校陪餐。游昕一行深入学校的食堂后厨 中国教育报-中国教育新闻网讯（记者 冯丽）近日，由西安交通大学（以下简称“西安交大”）、西安高压电器研究院股份有限公司与西安西电开关电气有限公司产学研深度融合的团队联合研发的“环保型发电机 中国教育报-中国教育新闻网讯（记者 任朝霞）11月11日，以“AI for Science双螺旋引擎驱动科研新范式”为主题的2024科学智能创新论坛在复旦大学枫林校区举行。论坛上，上海科学智能研究院（简称“上智 ◎摘 要 发挥高等教育在教育强国建设中的龙头作用，需要完善的高等教育财政政策作为坚实的保障。健全高等教育财政政策，要加大财政投入，建立多元化财政投资机制；调整转移支付体系，增强转移支付的 。本文链接：研究确定“背包问题”计算复杂性下限http://www.sushuapos.com/show-12-1209-0.html
声明：本网站为非营利性网站，本网页内容由互联网博主自发贡献，不代表本站观点，本站不承担任何法律责任。天上不会到馅饼，请大家谨防诈骗！若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。