The complexity of implementation of a system of~monomials in two variables by composition circuits

S. A. Korneev

Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 103-119.

Résumé

The computational complexity of systems of monomials by compositional circuits is investigated. In such a model, complexity is understood as the smallest number of composition operations required to compute a system of monomials. For this model we have found the computational complexity of a system of $p$ monomials in two variables up to a term that grows as $p$. By $l_{sh}(A)$ we mean the complexity of implementation of the system of monomials defined by the matrix $A$ by composition circuits. For any integer $a$ we assume $a^+=\max{(a,1)}$. Theorem. Let $A=(a_{ij})$ be a $(p \times q)$-matrix without zero rows and columns consisting of non-negative integers. Then $G(A) \le l_{sh}(A) \le G(A)+2p-3$, where \begin{equation*} G(A)=\max\limits_{(i_1, \ldots, i_p) \in S_p}{{\textstyle\sum\limits_{k=1}^{p}}{\left\lceil\log{\max{\left(\frac{a^+_{i_k 1}}{\max\limits_{l: l}{a^+_{i_l 1}}}, \frac{a^+_{i_k 2}}{\max\limits_{l: l}{a^+_{i_l 2}}}, 1\right)}}\right\rceil}}. \end{equation*} We also show that for composition circuits, in contrast to other models, the asymtotical growth of the computational complexity of system of monomials in two variables in the general case is not determined by any improper subset of this system of monomials.

Détail

Keywords: set of monomials, computation complexity, circuit complexity
Mots-clés : composition circuit.

Bibliographie

[1] Merekin Yu. V., “On the generation of words using the composition operation”, Diskretnyy Analiz i Issledovaniye Operatsiy. Ser. 1, 10:4 (2003), 70–78 (in Russian) | Zbl

[2] Trusevich E. N., “Complexity of certain systems of monomials in calculation by composition circuits”, Moscow University Math. Bull., 69:5 (2014), 193–197 | DOI | Zbl

[3] Korneev S. A., “On the complexity of implementation of a system of two monomials by composition curcuits”, Discr. Math. Appl., 31:2 (2021), 113–125 | Zbl

[4] Korneev S. A., “On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials”, Uchenye Zapiski Kazanskogo Universiteta. Ser. Fiziko-Matematicheskie Nauki, 162:3 (2020), 300–311 (in Russian)

[5] Shirshov A. I., “Some algorithmic problems for Lie algebras”, Sibirskiy Matematicheskiy Zhurnal, 3 (1962), 292–296 (in Russian) | Zbl

[6] Pippenger N., “On the evaluation of powers and monomials”, SIAM J. Comput., 9:2 (1980), 230–250 | DOI | Zbl

[7] Knuth D. E., The Art of Computer Programming, v. 2, Addison-Wesley, Reading, 1969 | Zbl

[8] Kochergin V. V., “On Bellman's and Knuth's problems and their generalizations”, J. Math. Sci., 233:1 (2018), 103–124 | DOI | Zbl

[9] Brauer A., “On addition chains”, Bull. AMS, 45 (1939), 736–739 | DOI

[10] Erdos P., “Remarks on number theory, III: On addition chains”, Acta Arithmetica, 6 (1960), 77–81 | DOI | Zbl

[11] Kochergin V. V., Kochergin D. V., “Improvement of the lower bound for the complexity of exponentiation”, Prikladnaya Diskretnaya Matematika, 2017, no. 38, 119–132 (in Russian) | Zbl

[12] Schönhage A., “A lower bound for the lenght of addition chains”, Theor. Comput. Sci., 1 (1975), 1–12 | DOI | Zbl

[13] Bellman R. E., “Addition chains of vectors (Advanced problems 5125)”, Amer. Math. Monthly, 70 (1963), 765

[14] Straus E. G., “Addition chains of vectors”, Amer. Math. Monthly, 71 (1964), 806–808

[15] Yao A. C.-C., “On the evaluation of powers”, SIAM J. Computing, 5 (1976), 100–103 | DOI | Zbl

[16] Gashkov S. B., Kochergin V. V., “On addition chains of vectors, gate circuits, and the complexity of computations of powers”, Siberian Adv. Math., 4:4 (1994), 1–16 | Zbl

[17] Kochergin V. V., “On the complexity of computations of monomials and tuples of powers”, Siberian Adv. Math., 6:1 (1996), 71–86 | Zbl

[18] Kochergin V. V., “Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman's and Knuth's problems”, J. Appl. Indust. Math., 9:1 (2015), 68–82 | DOI | Zbl

[19] Kochergin V. V., “On the complexity of computing systems of monomials in two variables”, Proc. VII Int. Conf. “Diskretnye Modeli v Teorii Upravlyayushchikh Sistem” (Pokrovskoe, March 4–6, 2006), MAKS Press Publ., M., 2006, 185–190 (in Russian)

[20] Sidorenko A. F., “Complexity of additive computations of a family of integer linear forms”, Zapiski Nauchnykh Seminarov LOMI, 105, 1981, 53–61 (in Russian) | Zbl

[21] Kochergin V. V., “Asymptotics of the complexity of systems of integer linear forms for additive computations”, J. Appl. Indust. Math., 1:3 (2007), 328–342 | DOI | Zbl

[22] Kochergin V. V., “On the complexity of joint computation of three elements of a free abelian group with two generators”, Diskretnyy Analiz i Issledovaniye Operatsiy. Ser. 1, 15:2 (2008), 23–64 (in Russian) | Zbl