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!