Solving the Rubik's Cube Optimally is NP-complete.

Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy

Browse the full STACS paper archive.