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