Computing Sequences with Addition Chains
Peter J. Downey, Benton L. Leong, Ravi Sethi · SIAM Journal on Computing · 1981
Given a sequence $n_1 , \cdots ,n_m $ of positive integers, what is the smallest number of additions needed to compute all m integers starting with 1? This generalization of the addition chain ($m = 1$) problem will be called the addition-sequence problem. We show that the sequence $\{ 2^0 ,2^1 , \cdots ,2^{n - 1} ,2^n - 1\} $ can be computed with $n + 2.13\sqrt n + \log n$ additions, and that $n + \sqrt n - 2$ is a lower bound. This lower bound result is applied to show that the addition-sequence problem is NP-complete.
Cited by 155 works. doi:10.1137/0210047
Authors
References
- Reducibility among Combinatorial Problems
- On addition chains
- A lower bound for the length of addition chains
- Remarks on number theory III. On addition chains
- Jahresbericht der Deutschen Mathematikervereinigung
- Addition Chain Methods for the Evaluation of Specific Polynomials
- Complexity measures and hierarchies for the evaluation of integers and polynomials