Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP. As Peter pointed out, my approach fails in some instances. One potential case of such an instance is where there exists a local maxima in the path length. By this I mean that it may take $S_A$ moves to solve the cube from configuration $A$, and either $S_A$ or $S_A - 1$ moves to solve the cube from any position which can be reached in one move from $A$. Now, this isn't necessarily such a problem if $S_A$ is maximum number of moves required to solve the cube in general (God's Number for that cube), but is definitely a problem if $S_A$ is strictly less than God's Number for that cube. So my question is do such local maxima exist? Even an answer for the $3 \times 3 \times 3$ cube would be of interest to me.
| |||||||||||||||
feedback
|
|
Asking Tomas Rokicki this question immediately yielded the correct answer ("yes, local maxima exist"):
I don't see why this is the case for the half-turn metric; but for the quarter-turn metric it is clear. In a position with total symmetry, all neighboring positions must be at the same path length (since all moves are equivalent by symmetry). So a position with total symmetry must be either a local maximum or a strict local minimum. But strict local minima cannot exist... there has to be some move that reduces the distance to the solved state, just by the definition of the distance. The symmetry argument translates to the $n \times n \times n$ cube, as does the example position provided. | |||||
|
feedback
|
|
Here's an extremely heuristic argument that suggests where local maxima may be found. Let $N_d$ be the number of positions that require exactly $d$ moves to solve. Each move from such a position takes the cube to distance $d-1$, $d$, or $d+1$; so there are a total of $N_{d-1} + N_d + N_{d+1}$ positions that are accessible. There are $M$ moves from each position, leading to $M$ new positions; a position at distance $d$ is a local maximum when none of these $M$ positions are at distance $d+1$. If we take these positions to be drawn uniformly at random from the accessible positions (which, of course, they aren't; this is the heuristic part), we have: $$ \begin{eqnarray} X_d &=& P\left[\text{ a given position at }d\text{ is a local max }\right] \\ &=& \left(\frac{N_{d-1} + N_d}{N_{d-1} + N_d + N_{d+1}}\right)^M \\ &=& \left(1 + \frac{N_{d+1}}{N_{d-1} + N_d}\right)^{-M}. \end{eqnarray} $$ The expected number of local maxima at distance $d$ is $N_d X_d$. For the $3 \times 3 \times 3$ cube, the number of moves from a given position is $M=18$, and estimates for $N_d$ are provided at God's Number is 20. Using these values, we find the expected number of local maxima to be $N_{16} X_{16} = 0.2$, $N_{17} X_{17} = 9 \times 10^9$, and $N_{18} X_{18} = 1.5 \times 10^{19}$. So there are unlikely to be any local maxima for $d \le 16$. At $d=17$, the total number of positions is estimated to be $12 \times 10^{18}$, so one might expect to test a billion positions before finding a local maximum. Finally, at $d=18$, one expects a local maximum in every twenty positions. | |||
feedback
|
