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

I spent a few hours today working through the addition chain problem. Given the starting number 1, how many additions are required to get to some target natural number n? For example, to make 5, we need three additions:

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

To make 15, we need five:

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

On the Wikipedia page for addition chains there is a citation that shows that finding an addition chain of some length that has to pass through a series of values is known to be $NP$-complete. However, I can't seem to find a reference anywhere that suggests that the addition chain problem starting purely from 1 is known to be $NP$-hard or not. Is it known whether or not this problem is $NP$-hard? Or is this still an open problem?

Thanks!

-
you miscounted, to make $15$, you need five. –  Patrick Da Silva Feb 16 '12 at 6:41

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)..."

-

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*}

-
The algorithm is (always) fast, but it is only an approximation. The problem asks for the minimal decomposition, which for 15 would be of size 5, not 6. –  Mike B. Feb 16 '12 at 6:59
This was too long for a comment ; I'd have rather answer it. I pointed out that it wasn't optimal. –  Patrick Da Silva Feb 16 '12 at 7:07
Sorry, maybe misunderstood 'optimal'. I mentioned the approximation, because that refers to the output of the function, whereas (to my understanding in complexity theory) optimal refers to the complexity of the function itself. I wanted to clarify that, without any discredit to your answer. –  Mike B. Feb 16 '12 at 8:14
Then I will clarify that optimal stood here for "my algorithm is optimal if it finds a minimal decomposition at every integer". –  Patrick Da Silva Feb 16 '12 at 9:34