Existe-t-il des maxima locaux dans le nombre de mouvements requis pour résoudre un Rubik's Cube?

Peter Shor a soulevé un point intéressant concernant une tentative de répondre à une question précédente sur la complexité de la résolution du cube Rubiks . J'avais posté une tentative assez naïve de montrer qu'elle doit être contenue dans NP. Comme Peter l'a souligné, mon approche échoue dans certains cas. Un cas potentiel d'une telle instance est celui où il existe un maximum local dans la longueur du chemin. Par là , je veux dire que cela peut prendre se déplace pour résoudre le cube de la configuration , et soit ou se déplace pour résoudre le cube de toute position qui peut être atteint en un seul mouvement de . Maintenant, ce n'est pas nécessairement un tel problème si$n \times n \times n$$S_A$$A$$S_A$$S_A - 1$$A$$S_A$est le nombre maximum de mouvements requis pour résoudre le cube en général ( le nombre de Dieu pour ce cube), mais c'est certainement un problème si est strictement inférieur au nombre de Dieu pour ce cube. Ma question est donc de savoir si ces maxima locaux existent? Même une réponse pour le cube m'intéresserait.$S_A$$3 \times 3 \times 3$

En posant à Tomas Rokicki cette question a immédiatement donné la bonne réponse ("oui, des maxima locaux existent"):

Si une position présente une symétrie totale, il s'agit nécessairement d'un maximum local (tout sauf le début). Un peu de réflexion devrait expliquer pourquoi c'est le cas dans le QTM [quart de tour métrique]. Pour le HTM [métrique demi-tour] c'est un peu plus subtil mais pas trop mal.

...

Une telle position est pons asinorum, qui est la distance 12 en QTM et la distance 6 en HTM (U2D2F2B2L2R2).

Je ne vois pas pourquoi c'est le cas pour la métrique demi-tour; mais pour la métrique quart de tour, c'est clair. Dans une position avec une symétrie totale, toutes les positions voisines doivent avoir la même longueur de chemin (car tous les déplacements sont équivalents par symétrie). Ainsi, une position avec une symétrie totale doit être soit un maximum local soit un minimum local strict. Mais des minima locaux stricts ne peuvent pas exister ... il doit y avoir un mouvement qui réduit la distance à l'état résolu, juste par la définition de la distance. L'argument de symétrie se traduit par le cube , tout comme l'exemple de position fourni.$n \times n \times n$

Voici un argument extrêmement heuristique qui suggère où les maxima locaux peuvent être trouvés. Soit le nombre de positions qui nécessitent exactement d mouvements à résoudre. Chaque mouvement depuis une telle position amène le cube à la distance d - 1 , d ou d + 1 ; il y a donc un total de N d - 1 + N d + N d + 1 positions accessibles. Il y a M mouvements de chaque position, menant à M nouvelles positions; une position à distance $N_d$$d$$d-1$$d$$d+1$$N_{d-1} + N_d + N_{d+1}$$M$$M$$d$est un maximum local lorsqu'aucune de ces positions n'est à la distance d + 1 . Si nous prenons ces positions pour être tirées uniformément au hasard des positions accessibles (ce qui, bien sûr, elles ne le sont pas; c'est la partie heuristique), nous avons:$M$$d+1$

Le nombre attendu de maxima locaux à la distance est N d X d .$d$$N_d X_d$

Pour le cube , le nombre de mouvements à partir d'une position donnée est M = 18 , et les estimations pour N d sont fournies au nombre de Dieu est 20 . En utilisant ces valeurs, nous trouvons que le nombre attendu de maxima locaux est N 16 X 16 = 0,2 , N 17 X 17 = 9 × 10 9 et N 18 X 18 = 1,5 × 10 19 . Il est donc peu probable qu'il y ait des maxima locaux pour$3 \times 3 \times 3$$M=18$$N_d$$N_{16} X_{16} = 0.2$$N_{17} X_{17} = 9 \times 10^9$$N_{18} X_{18} = 1.5 \times 10^{19}$$d \le 16$$d=17$$12 \times 10^{18}$$d=18$