Question: Is optimally solving the n×n×n Rubik's Cube NP-hard?
Cited in: Algorithms for Solving Rubik's Cubes. Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow. arXiv:1106.5736v1
(Also pointed out in the question's answer by @Andy Drucker.)