New Results on R. Bellman’s and D. Knuth’s Problems
Received: 09 Nov 2026 Accepted: 09 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 27–45
Abstract
We consider Bellman’s problem on the complexity of computing a monomial in \(m\) variables, defined as the minimum number of multiplications required, and Knuth’s problem on the complexity of computing a set of \(m\) powers of a single variable. For every fixed real number \(a\ge 2\) and every positive function \(\varphi (m)\) satisfying \(\lvert \log \varphi (m)\rvert =o(\log m)\), we establish asymptotically tight bounds for the corresponding Shannon functions, which describe the maximum possible complexity when the exponents are bounded by \(A=\varphi (m)m^a\). As \(m\to \infty\), these functions are asymptotic to \(am\) and \((a-1)m\), respectively.
Keywords: addition chains, vector addition chains, Bellman’s problem, Knuth’s problem, circuit complexity.
BibTeX
@article{IS-Kochergin2026,
author = {Kochergin, Vadim Vasil'evich},
title = {{New Results on R. Bellman’s and D. Knuth’s Problems}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {27--45},
}
AMSBIB
\Bibitem{IS-Kochergin2026}
\by V.\,V.~Kochergin
\paper New Results on R. Bellman’s and D. Knuth’s Problems
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 27--45
\lang In Russian
RU