Is finding the length of the shortest addition chain for a number $n$ really $NP$-hard?

Solution 1:

MR2128857 (2006g:11247) Rizzo, Ottavio G.(I-MILAN) On the complexity of the 2k-ary and of the sliding window algorithms for fast exponentiation. (English summary) Riv. Mat. Univ. Parma (7) 3* (2004), 289–299 says, in part,

"Finding the shortest addition chain for a given integer $n$ is commonly considered to be a very hard problem (although it has not been proved it is NP-hard, as often---but erroneously---is reported in the literature referring to [P. Downey, B. Leong and R. Sethi, SIAM J. Comput. 10 (1981), no. 3, 638--646; MR0623072 (82h:68064)]: see the remarks in [D. J. Bernstein, "Pippinger's exponentiation algorithm'', draft, available at http://cr.yp.to/papers/pippenger.pdf] about this misconception)..."

Solution 2:

One very quick way to find such a decomposition : write $n$ in its binary decomposition $n = (1010010011\dots0101)_2$. Then write $$ 1+1 = 2, 2+2 = 4, \dots, 2^{n-1} + 2^{n-1} = 2^n$ $$ and then sum up the required powers of $2$.

It is not optimal, but I'm just saying it will be quick very often. For $15$ it gives $6$ : $15 = (1111)_2$, and \begin{align*} 1+1 & = 2 \\ 2+2 & = 4 \\ 4+4 & = 8 \\ 8+4 & = 12 \\ 12+2 & = 14 \\ 14 + 1 & = 15. \end{align*}