Is optimally solving the n×n×n Rubik's Cube NP-hard? Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube.  Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time algorithm?

[Some related results are described in my recent blog post.]
A new paper by Demaine, Demaine, Eisenstat, Lubiw, and Winslow makes partial progress on this question---it gives a polynomial-time algorithm for optimally solving $n \times O(1) \times O(1)$ cubes, and shows $\mathsf{NP}$-hardness for optimally solving what you might call "partially-colored" cubes.
It also shows that the $n \times n \times n$ cube's configuration space has diameter $\Theta(n^2/\log n)$.

Sweet!

One possible next question that their work seems to suggest: is there a fixed family of partially-colored $n \times n \times n$ cubes, one for each value of $n$, such that optimally solving from a given configuration is $\mathsf{NP}$-hard?