11
$\begingroup$

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!

  • 0
    you miscounted, to make $15$, you need *five*.2012-02-16

2 Answers 2

11

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

3

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

  • 0
    Then I will clarify that optimal stood here for "my algorithm is optimal if it finds a minimal decomposition at every integer".2012-02-16