An addition chain for computing a positive integer $n$ is a sequence of natural numbers starting with $1$ and ending with $n$, such that each number in the sequence is the sum of two previous numbers.
Question: Is this problem NP-complete?
Wiki says the following about this paper:
A number of other papers state that finding a shortest addition chain for a single number is NP-complete, citing this paper, but it does not claim or prove such a result.
(In fact, in this paper were proved NP-completeness the following generalization: to find a chain that simultaneously forms each of a sequence of values).
Should we add Addition chain problem to the list?
