Complejidad de las torres de Hanoi

Me encontré con las siguientes dudas sobre la complejidad de Towers of Hanoi , sobre las cuales quisiera sus comentarios.

¿Está en NP? Intento de respuesta: supongamos que Peggy (probador) resuelve el problema y lo envía a Victor (verificador). Víctor puede ver fácilmente que el estado final de la solución es correcto (en tiempo lineal), pero no tendrá más opción que pasar por cada uno de los movimientos de Peggy para asegurarse de que no hizo un movimiento ilegal. Como Peggy tiene que hacer un mínimo de 2 ^ | discos | - 1 movimientos (demostrable), Victor también tiene que seguir su ejemplo. Por lo tanto, Victor no tiene verificación de tiempo polinomial (la definición de NP), y por lo tanto no puede estar en NP.
¿Está en PSPACE ? Parece que sí, pero no puedo pensar en cómo extender el razonamiento anterior.
¿Es completo para PSPACE? Parece que no, pero solo tengo una idea vaga. La planificación automatizada, de la cual ToH es una instancia específica, se completa con PSPACE. Creo que la planificación tiene instancias mucho más difíciles que ToH.

Actualizado : Entrada = , el número de discos; Salida = configuración del disco en cada paso. Después de actualizar esto, me di cuenta de que este formato de entrada / salida no se ajusta a un problema de decisión. No estoy seguro de la formalización adecuada para capturar las nociones de NP, PSPACE, etc. para este tipo de problema. $n$

Actualización n. ° 2 : después de los comentarios de Kaveh y Jeff, me veo obligado a hacer que el problema sea más preciso:

Deje que la entrada sea el par de entradas donde es el número de discos. Si la secuencia de movimientos realizados por los discos se escribe en el formato (número de disco, de-peg, a-peg) (número de disco, de-peg, a-peg) ... desde el primer movimiento hasta el Por último, y codificado en binario, genera el bit . $(n,i)$ $n$ $i$

Avíseme si necesito ser más específico sobre la codificación. ¿Supongo que el comentario de Kaveh se aplica en este caso?

complexity-theory time-complexity PKG
fuente

¿podría definir el problema de Towers of Hanoi o vincularlo a una definición?

Kaveh

PKG, sé lo que es la Torre de Hanoi. Me refería a cuál es el problema computacional que quieres saber sobre su complejidad. ¿Cuál es la entrada? ¿Cuál es el resultado?

Kaveh

@Kaveh: Tu intención no estaba clara desde tu primer comentario

PKG

lo siento. Por cierto, hay clases de complejidad de funciones, generalmente tienen una F antes o después del nombre, verifique el zoológico de complejidad para ver las definiciones.

Kaveh

Así es el número entero también parte de la entrada?

i

$i$

JeffE

Respuestas:

No, el problema que has descrito es bastante fácil. La razón de alto nivel es que el índice tiene aproximadamente bits de longitud, por lo que podemos permitirnos pasar tiempo polinomial en . $i$ $n$ $n$

Considere el siguiente problema relacionado: Dados dos enteros y , describa el movimiento en la solución del rompecabezas -disk. El tamaño de entrada es , pero de hecho, solo importa el bit menos significativo de . Entonces, incluso si es significativamente menor que , podemos resolver este problema en el tiempo polinomial en . $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 es par, entonces el disco mueve la clavija a la clavija . $d+n$ $d$ $(-p\bmod 3)$ $((-p-1)\bmod 3)$

Podemos calcular fácilmente y en el tiempo recorriendo la representación binaria de desde el bit menos significativo hacia arriba. Eso es. $p$ $d$ $O(\log k)$ $k$

Ahora supongamos que usted realmente desea el ésimo bit en la secuencia de salida, donde es parte de la entrada en lugar de . Si cada giro se codifica utilizando el mismo número de bits, específicamente, bits para el número de disco, bits para la clavija inicial y bits para la clavija fija, entonces solo tenemos que calcular el movimiento, donde , y luego extrae el bit apropiado. (Observe que es lineal en el tamaño de entrada, ya que necesitamos saber para determinar la salida). $i$ $i$ $k$ $\lg(n+1)$ $2$ $2$ $k$ $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$ $\lg(n+1)+4$ $n$

Por otro lado, si estamos usando una representación de longitud variable para los números de disco, entonces podemos encontrar el número de movimiento en tiempo polinómico mediante búsqueda binaria. Necesitamos saber el número total de vueltas necesarias para mover los discos superiores , para todos los , pero esto viene dado por la recurrencia que podemos evaluar en tiempo polinómico mediante programación dinámica. Los detalles restantes se dejan como un ejercicio aburrido para el lector. $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)$

(Supongo que he cometido al menos un error de paridad o de error, pero espero que la idea principal sea clara).

JeffE
fuente