正在解一个3x3x3的魔方被最优分类为NP

Question

我写的是3x3x3魔方与计算理论的关系。我读过一些关于神数和最优解的文章，但我仍然不知道解一个魔方的最优解是P还是NP，如果是P，是否有一个算法可以在多项式时间内解它?

Answer 1

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

Answer 2

NxNxN魔方的最优解是np完全的…如本文所述https://arxiv.org/abs/1706.06708