Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

New Results on R. Bellman’s and D. Knuth’s Problems

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover