Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
you miscounted, to make $15$, you need five. –  Patrick Da Silva Feb 16 '12 at 6:41
add comment

2 Answers

up vote 8 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.