Es encontrar la longitud de la menor, además de cadena de un número $n$ muy $NP$-duro?

Question

Me pasé un par de horas al día de trabajo a través de la adición de la cadena de problema. Dado el número de partida 1, ¿cuántos adiciones son necesarios para llegar a algún destino número natural n? Por ejemplo, para hacer 5, necesitamos tres adiciones:

• 1 + 1 = 2
• 2 + 2 = 4
• 4 + 1 = 5

Para hacer 15, necesitamos cinco:

• 1 + 1 = 2
• 1 + 2 = 3
• 3 + 3 = 6
• 3 + 6 = 9
• 9 + 6 = 15

En la página de Wikipedia para la adición de cadenas hay una cita que muestra que la búsqueda de una adición de la cadena de cierta longitud que tiene que pasar a través de una serie de valores es conocido por ser $NP$-completa. Sin embargo, me parece que no puede encontrar una referencia en cualquier lugar que sugiere que la adición de la cadena de un problema de partida puramente de 1 es conocido por ser $NP$-duro o no. Se sabe si o no este problema es $NP$-duro? O es todavía un problema abierto?

Gracias!

Answer 1

MR2128857 (2006g:11247) Rizzo, Octavio G.(I-MILÁN) En la complejidad de los 2k-ary y de la ventana de desplazamiento de algoritmos para la exponenciación rápida. (Resumen en inglés). Riv. Mat. Univ. Parma (7) 3* (2004), 289-299 dice, en parte,

"La búsqueda de la menor, además de la cadena para un entero dado $n$ es comúnmente considerado un problema muy difícil (aunque no se ha probado que es NP-duro, como a menudo---aunque erróneamente---se informa en la literatura referente a la [P. Downey, B. Leong y R. Sethi, SIAM J. Comput. 10 (1981), no. 3, 638--646; MR0623072 (82h:68064)]: vea los comentarios en [D. J. Bernstein, "Pippinger del algoritmo de exponenciación", el proyecto, disponible en http://cr.yp.to/papers/pippenger.pdf] acerca de este error)..."

Answer 2

Una manera muy rápida para encontrar una descomposición : escribir $n$ en su binario de descomposición $n = (1010010011\dots0101)_2$. A continuación, escribir $$ 1+1 = 2, 2+2 = 4, \puntos, 2^{n-1} + 2^{n-1} = 2^n$ $$ y luego resumir los necesarios poderes de $2$.

No es la óptima, pero sólo estoy diciendo que va a ser rápido, muy a menudo. Para $15$ da $6$ : $15 = (1111)_2$, y \begin{align*} 1+1 & = 2 \\ 2+2 & = 4 \\ 4+4 & = 8 \\ 8+4 & = 12 \\ 12+2 & = 14 \\ 14 + 1 & = 15. \end{align*}