Are there local maxima in the number of moves required to solve a Rubik's Cube? 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.
Asking Tomas Rokicki this question immediately yielded the correct answer ("yes, local maxima exist"):


  If a position exhibits total
  symmetry, it is of necessity a local
  maximum (all except the start).  A
  little thought should make it clear
  why this is the case in the QTM [quarter-turn metric].  For
  the HTM [half-turn metric] it's a bit more subtle but not
  too bad.
  
  ...
  
  Such a position is pons asinorum,
  which is distance 12 in QTM and
  distance 6 in HTM (U2D2F2B2L2R2).


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.