<p>Computing Sequence <span class="math-container">$a_1, \ldots, a_n$</span> with addition chains (CSAC) is the problem of finding the shortest sequence  <span class="math-container">$b_1, \ldots, b_m$</span> with the following properties:</p>
<ol>
<li><span class="math-container">$b_1=1$</span>.</li>
<li>Every <span class="math-container">$b_i$</span> with <span class="math-container">$i&gt;1$</span>  is the sum of two previous numbers.</li>
<li>For every <span class="math-container">$a_j$</span> there exists <span class="math-container">$b_i$</span> s.t. <span class="math-container">$a_j=b_i$</span>.</li>
</ol>
<p>It is known that this problem is <a href="https://epubs.siam.org/doi/10.1137/0210047" rel="nofollow noreferrer">NP-hard.</a></p>
<p><strong>Question:</strong> Is this problem has a pseudo-polynomial algorithm (i.e. polynomial in <span class="math-container">$a_1 + \ldots a_n$</span>)?</p>
<p>UPD: I have understood that the problem is not trivial even if <span class="math-container">$n=1$</span>.</p>

CC BY-SA 4.0
2022-07-27T23:58:49.550Z
It shouldn’t be NP hard because there’s always a solution of size polylog(N) where N is the sum of ai’s
daniello
CC BY-SA 4.0
2022-07-28T03:18:39.013Z
@daniello the size of the solution depence on small $n$...
Alexey Milovanov
CC BY-SA 4.0
2022-08-02T14:37:25.320Z
I mean the number of $b_i$’s that are not equal to any $a_j$‘s.
daniello
CC BY-SA 4.0
2022-08-02T18:22:51.283Z
@daniello and why is it true?
Alexey Milovanov
CC BY-SA 4.0
2022-08-25T22:09:23.760Z
It isn’t (or rather I don’t see a proof and expect it to be false). My mistake was to assume that once we have all the powers of 2 we can make every bi in just one operation, which is total bull.
daniello
<np-hardness><np-complete>
Computing Sequences with Addition Chains In pseudopolynomial time?
Alexey Milovanov
# Computing Sequences with Addition Chains In pseudopolynomial time?

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

Computing Sequence $a\_1, \ldots, a\_n$ with addition chains (CSAC) is the problem of finding the shortest sequence $b\_1, \ldots, b\_m$ with the following properties:

1. $b\_1=1$.
2. Every $b\_i$ with $i>1$ is the sum of two previous numbers.
3. For every $a\_j$ there exists $b\_i$ s.t. $a\_j=b\_i$.

It is known that this problem is [NP-hard.](https://epubs.siam.org/doi/10.1137/0210047)

**Question:** Is this problem has a pseudo-polynomial algorithm (i.e. polynomial in $a\_1 + \ldots a\_n$)?

UPD: I have understood that the problem is not trivial even if $n=1$.

**Tags:** np-hardness, np-complete
> **Comments:**
> **username_1**: It shouldn’t be NP hard because there’s always a solution of size polylog(N) where N is the sum of ai’s  
> **username_0**: @daniello the size of the solution depence on small $n$...  
> **username_1**: I mean the number of $b_i$’s that are not equal to any $a_j$‘s.  
> **username_0**: @daniello and why is it true?  
> **username_1**: It isn’t (or rather I don’t see a proof and expect it to be false). My mistake was to assume that once we have all the powers of 2 we can make every bi in just one operation, which is total bull.  

---

## 0 answers

