Complexité des tours de Hanoi

J'ai rencontré les doutes suivants sur la complexité des tours de Hanoi , sur lesquelles j'aimerais avoir vos commentaires.

Est-ce en NP? Tentative de réponse: supposons que Peggy (prouveur) résout le problème et le soumette à Victor (vérificateur). Victor peut facilement voir que l'état final de la solution est bon (en temps linéaire) mais il n'aura pas d'autre choix que de passer par chacun des mouvements de Peggy pour s'assurer qu'elle n'a pas fait un mouvement illégal. Puisque Peggy doit faire un minimum de 2 ^ | disques | - 1 coups (prouvable), Victor doit lui aussi emboîter le pas. Ainsi Victor n'a pas de vérification de temps polynomiale (la définition de NP), et ne peut donc pas être dans NP.
Est-ce dans PSPACE ? Semble oui, mais je ne peux pas penser à la façon d'étendre le raisonnement ci-dessus.
Est-il complet sur PSPACE? Semble pas, mais je n'ai qu'une vague idée. La planification automatisée, dont ToH est une instance spécifique, est complète avec PSPACE. Je pense que la planification a des instances beaucoup plus difficiles que ToH.

Mis à jour : Input = $n$ , le nombre de disques; Sortie = configuration du disque à chaque étape. Après avoir mis à jour cela, j'ai réalisé que ce format d'entrée / sortie ne correspond pas à un problème de décision. Je ne suis pas sûr de la bonne formalisation pour capturer les notions de NP, PSPACE, etc. pour ce type de problème.

Mise à jour # 2 : Après les commentaires de Kaveh et Jeff, je suis obligé de rendre le problème plus précis:

Soit l'entrée la paire d' $(n,i)$ où $n$ est le nombre de disques. Si la séquence de mouvements effectuée par les disques est écrite au format (numéro de disque, à partir de la cheville, à la cheville) (numéro de disque, de la cheville, à la cheville) ... du premier mouvement à la enfin, et codé en binaire, émet le $i$ ème bit.

Faites-moi savoir si j'ai besoin d'être plus précis sur l'encodage. Je suppose que le commentaire de Kaveh s'applique dans ce cas?

complexity-theory time-complexity PKG
la source

pourriez-vous s'il vous plaît définir le problème des tours de Hanoi ou un lien vers une définition?

Kaveh

PKG, je sais ce que c'est la Tour de Hanoi. Je voulais dire quel est le problème de calcul que vous voulez connaître sa complexité? Quelle est l'entrée? Quelle est la sortie?

Kaveh

@Kaveh: Votre intention n'était pas claire à partir de votre premier commentaire

PKG

Pardon. Btw, il existe des classes de complexité de fonction, elles ont généralement un F avant ou après le nom, consultez le zoo de complexité pour les définitions.

Kaveh

i

$i$

Réponses:

$i$ $n$ $n$

$n$ $k$ $k$ $n$ $\lg n + \lg k < n + \lg k$ $n$ $\lg k$ $n$ $O(\log k)$

$0$ $k = (2p+1)\cdot 2^d$ $p$ $d$ $k$

$d+n$ $d$ $(p\bmod 3)$ $((p+1)\bmod 3)$
Si est pair, le disque se déplace de la forme peg vers peg . $d+n$ $d$ $(-p\bmod 3)$ $((-p-1)\bmod 3)$

Nous pouvons facilement calculer et dans le temps en parcourant la représentation binaire de du bit le moins significatif vers le haut. C'est ça. $p$ $d$ $O(\log k)$ $k$

Supposons maintenant que vous vouliez vraiment le ème bit dans la séquence de sortie, où fait partie de l'entrée au lieu de . Si chaque tour est codé en utilisant le même nombre de bits - en particulier, bits pour le numéro de disque, bits pour le from-peg et bits pour le to-peg - alors nous devons simplement calculer le ème mouvement, où , puis extraire le bit approprié. (Notez que est linéaire dans la taille d'entrée, car nous devons connaître pour déterminer la sortie.) $i$ $i$ $k$ $\lg(n+1)$ $2$ $2$ $k$ $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$ $\lg(n+1)+4$ $n$

D'un autre côté, si nous utilisons une représentation de longueur variable pour les nombres de disques, alors nous pouvons trouver le nombre de déplacements en temps polynomial par recherche binaire. Nous devons connaître le nombre total de tours nécessaires pour déplacer les premiers disques, pour tous les , mais cela est donné par la récurrence que nous pouvons évaluer en temps polynomial par programmation dynamique. Les autres détails sont laissés comme un exercice ennuyeux pour le lecteur. $k$ $m$ $m\le k$

M (m) = 2 M (m - 1) + (\#bits to record moving disk m)

$M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m)$

(Je suppose que j'ai fait au moins une erreur de coup par coup ou de parité, mais j'espère que l'idée principale est claire.)

JeffE
la source