On the \(\lambda\)-complexity of a system of four monomials in three variables
Received: 24 Oct 2026 Revised: 28 Oct 2026 Accepted: 07 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 172–175
Abstract
We study the minimum number of multiplications and exponentiations to rational powers in the interval \((0,2)\) sufficient to compute an arbitrary system of four monomials in three variables. This number is shown to be \(\log _2 D(A)+O(1)\), where \(A\) is the nonnegative integer matrix of exponents with no zero rows, and \(D(A)\) is the maximum absolute value of all minors of \(A\).
Keywords: circuit complexity, Pippenger's problem, computational complexity, systems of monomials, λ-circuits.
BibTeX
@article{IS-Kochergin-Yarygin2026,
author = {Kochergin, Vadim Vasil'evich and Yarygin, Oleg Vital'evich},
title = {{On the $\lambda $-complexity of a system of four monomials in three variables}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {172--175},
}
AMSBIB
\Bibitem{IS-Kochergin-Yarygin2026}
\by V.\,V.~Kochergin, O.\,V.~Yarygin
\paper On the $\lambda $-complexity of a system of four monomials in three variables
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 172--175
\lang In Russian
RU