6

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?

Alexey Milovanov
  • 2,003
  • 10
  • 21

1 Answers1

4

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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149