中新网北京5月27日电 (记者 孙自法)“背包问题”是核算机科学中经典的NP完全问题(非确认性图灵机多项式复杂度求解的决议问题)之一，其相关研讨长期以来备受科学家重视。

　　记者5月27日从我国科学院金属研讨所得悉，该所张志东研讨员最近在核算机科学根底理论范畴获得一项突破性发展，初次准确确认了“背包问题”的核算复杂度下限，浅显而言便是发现核算速度极限。

　　我国科学家破解“背包问题”复杂度之谜的这项根底研讨成果论文，近来在美国数学科学研讨所出版社(AIMS)《数学》期刊宣布。

　　张志东研讨员科普解读说，“背包问题”假定你有一个容量有限的背包，面前摆着N件价值不同、分量各异的物品，怎么正确的挑选物品组合才能使总价值最大化？这个看似简略的挑选问题，实则隐藏核算玄机：当物品数量逾越必定规划后，即便运用最先进核算机也需求消耗天文数字时刻求解，而“核算复杂度下限”便是处理问题所需的最少时刻。

　　在现实生活中，包含在物流运送范畴怎么优化集装箱装载计划、在金融出资范畴怎么构建收益最大化的出资组合、材料科学范畴怎么寻觅最优原子摆放方法等，都触及“背包问题”。

　　我国科学院金属研讨所介绍，在10余年三维伊辛模型研讨工作的根底上，张志东研讨员此次建立起“背包问题”与自旋玻璃三维伊辛模型的联络，依据两个问题的联系确认“背包难题”的核算复杂度的下限。

　　他经过把每个物品的挑选(取或不取)对应为微观粒子的两种自旋状况，将价值最大化问题转化为寻觅体系最低能量状况，发现“肯定极小中心模型”，提醒核算复杂度的根源来自三维晶格中自旋摆放的特别拓扑结构。

　　进一步经过构建核算复杂度相图，张志东初次描绘出NP完全问题与NP中心问题(在NP类中既不是P类问题也不是NP完全问题的问题)的分界线，然后确认复杂度下限，证明最优算法的时刻复杂度至少为(1+ε)^N(ε为趋近0的正数)，明显优于现有1.3^N的算法。

　　业界专家称，“背包问题”能够被映射为许多其他的科学问题，我国科学家此次破解“背包问题”复杂度之谜的研讨定论能够直接推广应用，将助力处理核算机、物理、化学、生物、数学以及材料科学范畴一系列相关根底科学问题。(完)

　　违法和不良信息告发电话： 告发邮箱：报受理和处置管理办法总机：86-10-87826688