The Complexity of Rubik's Cube

In my book I use Rubik's Cube as an example of a puzzle we can computationally solve efficiently (as opposed to Sudoku or Rush Hour). How does this square with the new result of Erik Demaine, Sarah Eisenstat and Mikhail Rudoy that finding the shortest solution is NP-complete? New Scientist now proclaims It’s not you – solving a Rubik’s cube quickly is officially hard. No, it's still you.

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² 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²/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.