<p>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.</p>

CC BY-SA 4.0
2022-07-10T13:37:44.097Z
2022-07-10T15:01:41.833Z
2022-07-10T15:01:41.833Z
Mohammad Al-Turkistany
<p>An addition chain for computing a positive integer <span class="math-container">$n$</span> is a sequence of natural numbers starting with <span class="math-container">$1$</span> and ending with <span class="math-container">$n$</span>, such that each number in the sequence is the sum of two previous numbers.</p>
<p>Question: Is this problem NP-complete?</p>
<p>Wiki says the following about <a href="https://epubs.siam.org/doi/10.1137/0210047" rel="noreferrer">this paper</a>:</p>
<p><em>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.</em></p>
<p>(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).</p>
<p>Should we add Addition chain problem to <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc">the list</a>?</p>

<np-hardness><np-complete>
Finding a minimal addition chain for a given number
Alexey Milovanov
# Finding a minimal addition chain for a given number

(Asked by: username_0 on 2022-07-10)

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](https://epubs.siam.org/doi/10.1137/0210047):

*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](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc)?

**Tags:** np-hardness, np-complete


---

## 1 answers

### Answer by username_1 on 2022-07-10. Score: 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.


---

