快速解開魔方本來就很難

轉動綠色方塊以解開魔方。圖片來源：Marko Mrkonjic/PIXSELLL

如果你覺得解開一個魔方存在困難，那麼你的感覺是對的，數學可以提供支撐。近日一項研究表明，能否通過一定次數的步驟解開任意尺寸的被打亂的魔方，這被稱為NP—完全，它是一個即便對數學家來說也很難解開的問題。

為了證明該問題是NP—完全，美國麻省理工學院研究人員Erik Demaine、Sarah Eisenstat和Mikhail Rudoy表明，弄清如何通過最少的步驟讓魔方的一面擁有任何數量的方塊，還能夠讓人們找到解開另一個非完全多項式的問題：漢彌爾頓路徑問題。

該問題為：是否有一條路徑能夠確切地到達由一系列點組成、並由線段相連的圖中的每個頂點，如三角形、五角星或是社交網路如臉譜網中更廣泛的連接點。

它讓人想起旅行推銷員問題，該問題旨在找到一次性訪問若干城市的最短路徑，可能是最為著名的NP—完全問題。「描述它如何運作非常簡練。」伊利諾伊大學香檳分校的Jeff Erickson說。

NP-完全問題非常容易檢驗，如果你得到一個初步解決方案，但隨著輸入數據的增加，需要解開它們的時間會激增，至少對於今天人們所知道的算式是這樣的。同時，用算式在合理時間內解開程序的問題所基於的數據輸入被稱為P。

研究人員仍不確定是否存在算式能夠更快地解開NP-完全問題。這個問題通常被稱為P vs NP問題，是目前尚未解決的最重要的數學問題之一，該問題解題人將能從馬薩諸塞州劍橋克雷數學研究所獲得1000萬美元的獎金。

每個標準的3x3x3魔方無論如何被打亂，從任何一個未知開始最多都能夠通過20步被解開。2010年，程序員將20稱為彩色魔方「上帝的數字」，他們選擇這一命名表明即便是神也不能更快地解開魔方。

一年後，Demaine、Eisenstat和同事設計了一個方程式以解開任何邊長的魔方，他們發現一個邊長為n的魔方多需要的步驟正比於n2（2上標）/log n。

找到n=3魔方的「上帝的數字」花費了若干年的計算時間，Demaine推測，找到n=4魔方的「上帝的數字」要花費的時間還會比這長得多。「我猜想，它可能永遠不能被解開。」他說。「『上帝的數字』是大多數被打亂的魔方的最高上限，但很多魔方並不需要花費那麼多步驟。弄清楚任何一個魔方結構是否能夠採取更少的步驟非常棘手。」

所以，如果你解開魔方所費時間比較久，請勿沮喪，它不是你一個人的問題。「現在你有了借口：魔方本身就很難解開。」Rudoy說。你不必快速解開它，因此可以坐下來慢慢思考。（晉楠）

更多閱讀

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！