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?


1 Answer 1


The problem is not known to be NP-complete. Some references assume erroneously NP-completness. Furthermore, technically, minimum addition chain is search problem. I guess you are asking for NP-hardness proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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