院况简介
1949年,伴随着新中国的诞生,中国科学院成立。
作为国家在科学技术方面的最高学术机构和全国自然科学与高新技术的综合研究与发展中心,建院以来,中国科学院时刻牢记使命,与科学共进,与祖国同行,以国家富强、人民幸福为己任,人才辈出,硕果累累,为我国科技进步、经济社会发展和国家安全做出了不可替代的重要贡献。 更多简介 +
院领导集体
创新单元
科技奖励
科技期刊
工作动态/ 更多
中国科学院学部
中国科学院院部
语音播报
如果你觉得解开一个魔方存在困难,那么你的感觉是对的。近日一项研究表明,能否通过一定次数的步骤解开任意尺寸的被打乱的魔方——这被称为NP—完全,是一个即便对数学家来说也很难解开的问题。
为了证明该问题,美国麻省理工学院研究人员Erik Demaine、Sarah Eisenstat和Mikhail Rudoy表示,弄清如何通过最少的步骤让魔方的一面拥有任何数量的方块,还能够让人们找到解开另一个非完全多项式的问题:汉弥尔顿路径问题。
该问题为:是否有一条路径能够确切地到达由一系列点组成,并由线段相连的图中的每个顶点,如三角形、五角星或是社交网络如脸谱网中更广泛的连接点。
它让人想起旅行推销员问题,该问题旨在找到一次性访问若干城市的最短路径,这可能是最为著名的NP—完全问题。“描述它如何运作非常简练。”伊利诺伊大学香槟分校的Jeff Erickson说。
NP—完全问题非常容易检验,如果你得到一个初步解决方案,但随着输入数据的增加,需要解开它们的时间会激增,至少对于今天人们所知道的算式是这样的。同时,用算式在合理时间内解开程序的问题所使用的数据输入被称为P。
研究人员仍不确定是否存在算式能够更快地解开NP—完全问题。这个问题通常被称为P vs NP问题,是目前尚未解决的最重要的数学问题之一,该问题解题人将能从马萨诸塞州剑桥克雷数学研究所获得1000万美元的奖金。
每个标准的3×3×3魔方无论如何被打乱,从任何一个未知开始最多都能够通过20步被解开。2010年,程序员将20称为彩色魔方“上帝的数字”,他们选择这一命名表明即便是神也不能更快地解开魔方。
一年后,Demaine、Eisenstat和同事设计了一个方程式以解开任何边长的魔方,他们发现一个边长为n的魔方需要的步骤正比于n2/log n。
找到n=3魔方的“上帝数字”花费了若干年的计算时间,Demaine推测,找到n=4魔方的“上帝数字”要花费的时间比这长得多。“我猜想,它可能永远不能被解开。”他说,“‘上帝的数字’是大多数被打乱的魔方的最高上限,但很多魔方并不需要花费那么多步骤。弄清楚任何一个魔方结构是否能够采取更少的步骤非常棘手。”
所以,如果你解开魔方所费时间比较久,请勿沮丧,它不是你一个人的问题。“现在你有了借口:魔方本身就很难解开。”Rudoy说。你不必快速解开它,因此可以坐下来慢慢思考。
扫一扫在手机打开当前页
© 1996 - 中国科学院 版权所有 京ICP备05002857号-1 京公网安备110402500047号 网站标识码bm48000002
地址:北京市西城区三里河路52号 邮编:100864
电话: 86 10 68597114(总机) 86 10 68597289(总值班室)
编辑部邮箱:casweb@cashq.ac.cn
© 1996 - 中国科学院 版权所有 京ICP备05002857号-1 京公网安备110402500047号 网站标识码bm48000002
地址:北京市西城区三里河路52号 邮编:100864
电话: 86 10 68597114(总机) 86 10 68597289(总值班室)
编辑部邮箱:casweb@cashq.ac.cn
© 1996 - 中国科学院 版权所有
京ICP备05002857号-1
京公网安备110402500047号
网站标识码bm48000002
地址:北京市西城区三里河路52号 邮编:100864
电话:86 10 68597114(总机)
86 10 68597289(总值班室)
编辑部邮箱:casweb@cashq.ac.cn