快速解开魔方本来就很难
时间:2017-12-08

  快速解锁魔方始终是困难的 - 新闻 - 科学网

  如果你觉得难以解决一个难题,那么你觉得正确和数学可以提供支持。最近的一项研究表明,通过一定数量的步骤解开任意大小的无序立方体,可以完全解决NP问题,这是数学家难以解决的问题。

  为了证明这个问题是NP完全问题,埃里克·德曼,萨拉Eisenstat和米哈伊尔Rudoy,研究人员在麻省理工学院,显示如何找出如何有任何数量的立方体的立方体的一侧用最少的数并且使得有可能找到另一个不完全多项式问题的解:Hamilton路径问题。

  问题是,是否有一条路径完全到达一个图形中的每个顶点,这个顶点由一系列点组成,并且通过段连接,比如三角形,五角星形或者社交网络中的更广泛的连接点,例如Facebook 。

  这让人想起旅行商问题,这个问题是为了找到一次去几个城市的最短路径,可能是最着名的NP完全问题。它描述了它是如何工作的非常简洁。伊利诺伊大学香槟分校的杰夫·埃里克森说。

  NP完全问题很容易测试。如果你得到了一个初步的解决方案,随着输入数据的增加,解锁它们所花费的时间将大大增加,至少对于今天的人们来说是如此。同时,在合理时间内解决程序问题所依据的数据录入称为P.

  研究人员仍然不确定公式的存在是否能更快地解决NP完全问题。这个问题,通常被称为P对NP,是最重要的数学问题之一,还有待解决,解决者将从马萨诸塞州的剑桥克莱数学研究所获得1000万美元的奖金。

  任何标准的3x3x3魔方都会被打乱,最多可以达到20级,2010年,程序员调用了20个彩色立方体神的数量,他们选择的名字表明即使上帝也不能更快地解锁立方体。

  一年后,Demaine,Eisenstat及其同事设计了一个方程来解决任何边长的立方体。他们发现,边n所在立方体所需的步数与n2(2上标)/ log n成正比。

  发现有3个魔方的魔方花费了数年的计算时间,Demaine推测,找到上帝的魔方数目将需要更长的时间,我想这可能永远不会解开。上帝的数字是大多数被破坏的立方体的最大天花板,但是许多立方体没有多少步骤。弄清楚任何一个立方体结构是否可以采取更少的步骤是棘手的。

  所以,如果你花费很长的时间来解开魔方,那么不要感到沮丧,这不是你个人的问题,现在你有了一个借口:魔方本身很难解决,Rudoy说,你不必很快解开它所以你可以坐下来慢慢思考(金楠)

  阅读更多

  新科学家网站相关报告(英文)