1

我正在写一些关于3x3x3魔方和计算理论的关系。我读过一些关于上帝的数字和最佳解决方案的文本，但我仍然无法弄清楚是否以最佳方式解决了一个魔方，P或者NP，如果是P，是否有一种算法可以在多项式时间内解决它？

4

2 回答 2

2

求解 3x3x3 魔方是 O(1)。求解 NxNxN 魔方几乎可以肯定是 NP-hard，但我不确定是否有严格的证明。也许开始看这里：https : //cstheory.stackexchange.com/questions/783/is-optimally-solving-the-n ×n×n-rubiks-cube-np-hard

于 2016-10-18T13:37:05.823 回答
0

NxNxN 魔方的最优解是 NP-Complete ... 如本文所述https://arxiv.org/abs/1706.06708

于 2018-11-03T23:36:59.983 回答