To study the complexity of Rubik's cube we can't just fixate on the 3x3x3 cube with its finite state space but on the general NxNxN cube. (One could also generalize to 3-sided hypercubes in N dimensions but good luck constructing a 3x3x3x3x3 Rubik's cube.) For a given mixed-up NxNxN cube we can find in polynomial time a polynomial number of steps to return the cube to the original state. A mixed-up cube is just a member of the permutation group of the 6N

^{2}small squares and we want to find a sequence of generators (allowable rotations of the cube) that yield the mixed-up cube. Group theorists have come up with very efficient algorithms to find these sequences which we can apply in reverse to solve the cube.

Group theory does not necessarily come up with the shortest possible sequence and only in 2010 did we discover that solving the worst-case 3x3x3 cube, the so-called "God's Number", required 20 moves. A year later Demaine et. al showed that the minimum sequence for an NxNxN cube is Θ(N

^{2}/log N).

Two weeks ago Demain, Eisenstat and Rudoy posted their proof that given a fixed NxNxN cube finding the shortest sequence in NP-complete. Their proof is combinatorial, showing that solving an NxNx1 cube is NP-complete and reducing to the NxNxN cube.

So there you have it, solving a generalized Rubik's cube is easy but finding the shortest possible solution is hard. Despite Rubik's Cube achieving popularity during my nerdy high school days, I never had the patience to solve it, but that's just me.

Reminds me of the various sorting-by-transposition questions:

ReplyDeletesorting is easy/efficient, one can always do it in O(n) steps, but finding the shortest sequence of sorting moves is NP-hard and often hard to approximate as well.

Coloring the edges of a graph is also easy, even with only one color more than necessary, but to decide whether \Delta or \Delta + 1 colors are needed is NP-hard. Here the gap is probably narrower than for Rubik's cube.

ReplyDeleteI would say the point is the difference between "solving the Cube problem" and "solving the shortest solution problem". No whiz-kid can, on promise that there is a 19-move solution, find it within 30 seconds...

ReplyDelete