<p>Optimal solution of a NxNxN Rubik's cube is NP-Complete ... as discussed in this paper <a href="https://arxiv.org/abs/1706.06708" rel="nofollow noreferrer">https://arxiv.org/abs/1706.06708</a></p>
Is solving a 3x3x3 rubiks cube optimally classified as NP?
<p>I'm writing something about the relation of <code>3x3x3</code> Rubiks cube and theory of computation. I've read some texts talking about the god's number and optimally solutions, but I still can't figure out if solving a rubiks cube optimally is <code>P</code> or <code>NP</code>, if it is <code>P</code>, there is an algorithm to solve it in polynomial time? </p>