快速解开魔方本来就很难

转动绿色方块来解魔方。资料来源:Marko Mrkonjic/PIXSELL

如果你认为解魔方很难，那么你是对的，数学可以提供支持。最近的一项研究表明，数学家很难通过一定数量的步骤来解决被称为NP完全的任意大小的难题。

为了证明这个问题是NP完全的，麻省理工学院的研究人员埃里克·德梅恩、萨拉·艾森斯塔特和米哈伊尔·鲁多伊指出，找出如何用最少的步骤使魔方的一边有任意数量的正方形，也可以帮助人们找到解决另一个不完全多项式问题的方法:哈密尔顿路径问题。

问题是，在一个由一系列点组成并由线段连接的图中，是否有一条路径可以精确地到达每个顶点，比如三角形、五角星形或社交网络中更广泛的连接点，比如脸书。

它让人们想起旅行推销员问题，这个问题旨在寻找一次游览几个城市的最短路径，可能是最著名的NP完全问题。"描述它是如何工作的非常简洁。"伊利诺伊大学香槟分校的杰夫·埃里克森说。

完整的问题很容易测试。如果你得到了一个初步的解决方案，但是随着输入数据的增加，解决它们所需的时间将会激增，至少对于今天已知的公式来说是这样。同时，利用公式在合理时间内解决程序问题的数据输入称为p。

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

每一个标准的3x3x3魔方都可以从任何未知开始，最多用20个步骤来解决。2010年，程序员称20色魔方为“上帝的数字”他们选择这个名字是为了表明即使是上帝也不能更快地解决魔方。

一年后，德米恩、艾森斯塔特和他们的同事设计了一个方程来求解任意边长的魔方。他们发现边长为n的魔方所需的步数与N2(上标2)/对数n成正比

找到n=3魔方的“上帝数”需要多年的计算。德梅因推测，找到n=4魔方的“上帝数”需要更长的时间。“我想这个问题可能永远也解决不了。”他说。“‘上帝的数量’是大多数被破坏的魔方的最高限制，但是许多魔方不需要这么多步骤。很难发现任何一个魔方结构能少走几步。”

因此，如果解决魔方需要很长时间，不要气馁，这不仅仅是你的问题。“现在你有了一个借口:魔方本身很难解决。”鲁多伊说。你不必很快解开它，所以你可以坐下来慢慢思考。(晋南)

阅读更多

新科学家网站上的相关报道