О сложности реализации системы из трёх мономов схемами композиции

О сложности реализации системы из трёх мономов схемами композиции

Корнеев С. А.
Дискретный анализ и исследование операций, 32, 4, 146-171 (2025)
Скачать статью

УДК 519.71 
DOI: 10.33048/daio.2025.32.838

Аннотация:

Исследуется сложность реализации систем мономов схемами композиции. Под сложностью в этой модели понимается минимальное число операций, необходимое для вычисления системы мономов по переменным, при этом допускается многократное использование результатов промежуточных вычислений. Основные результаты данной работы: для произвольной системы из трёх мономов без нулевых степеней установлена асимптотика сложности их совместной реализации схемами композиции; для произвольной системы из трёх мономов от трёх переменных без нулевых степеней установлена формула, выражающая сложность их совместной реализации схемами композиции с точностью до единицы. 

Табл. 1, библиогр. 21.

Литература:
  1. Ширшов А. И. Некоторые алгоритмические проблемы для алгебр Ли // Сиб. мат. журн. 1962. Т. 3, № 2. С. 292–296.
     
  2. Мерекин Ю. В. О порождении слов с использованием операции композиции // Дискрет. анализ и исслед. операций. Сер. 1. 2003. Т. 10, № 4. С. 70–78.
     
  3. Merekin Yu. V. Some bounds on the complexity of words // Southeast Asian Bull. Math. 2006. V. 30, No. 6. P. 1081–1121.
     
  4. Трусевич Е. Н. О сложности реализации схемами композиции систем из двух мономов от двух переменных // Мат. VIII Молодёж. науч. шк. по дискретной математике и её приложениям. Ч. 2 (Москва, Россия, 24–29 окт. 2011 г.). М.: ИПМ РАН, 2011. С. 40–44.
     
  5. Трусевич Е. Н. О сложности вычисления некоторых систем одночленов схемами композиции // Вестн. Моск. ун-та. Сер. 1. 2014. № 5. С. 18–22.
     
  6. Корнеев С. А. О сложности реализации системы из двух мономов схемами композиции // Дискрет. математика. 2020. Т. 32, № 2. С. 15–31.
     
  7. Корнеев С. А. Об асимптотическом поведении функций шенноновского типа, характеризующих сложность вычисления систем мономов // Учён. зап. Казан. ун-та. Сер. Физ.-мат. науки. 2020. Т. 162, № 3. С. 300–310.
     
  8. Корнеев С. А. О сложности реализации системы мономов от двух переменных схемами композиции // Прикл. дискрет. математика. 2021. № 53. С. 103–119.
     
  9. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во Моск. ун-та, 2024. 124 с.
     
  10. Сэвидж Дж. Э. Сложность вычислений. М.: Факториал, 1998. 368 с.
     
  11. Храпченко В. М. Нижние оценки сложности схем из функциональных элементов // Кибернетический сборник. Новая сер. Вып. 21. М.: Мир, 1984. С. 3–54.
     
  12. Кочергин В. В. Задачи Р. Беллмана и Д. Кнута и их обобщения: Сложность аддитивных вычислений. Saarbr¨ucken: Palmarium Acad. Publ., 2012. 396 с.
     
  13. Кочергин В. В. О задачах Беллмана и Кнута и их обобщениях // Фундамент. и прикл. математика. 2015. Т. 20, № 6. С. 159–188.
     
  14. Кочергин В. В. Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках // Математические вопросы кибернетики. Вып. 20. М.: Физматлит, 2022. С. 119–256.
     
  15. Кочергин В. В. О сложности вычисления систем одночленов от двух переменных // Тр. VII Междунар. конф. «Дискретные модели в теории управляющих систем» (Покровское, Россия, 4–6 мар. 2006 г.). М.: МАКС Пресс, 2006. С. 185–190.
     
  16. Сидоренко А. Ф. Сложность аддитивных вычислений семейства целочисленных линейных форм // Зап. науч. сем. ЛОМИ. Т. 105. Теоретические применения методов математической логики. III. Л.: Наука, 1981. С. 53–61.
     
  17. Knuth D. E., Papadimitriou C. H. Duality in addition chains // Bull. Eur. Assoc. Theor. Comput. Sci. 1981. V. 13. P. 2–4.
     
  18. Olivos J. On vectorial addition chains // J. Algorithms. 1981. V. 2, No. 1. P. 13–21.
     
  19. Кочергин В. В. О сложности совместного вычисления трёх одночленов от трёх переменных // Математические вопросы кибернетики. Вып. 15. М.: Физматлит, 2006. С. 79–154.
     
  20. Кочергин В. В. Простое доказательство верхней оценки сложности вычисления трёх одночленов трёх переменных // Вестн. Моск. ун-та. Сер. 1. 2019. № 2. С. 3–8.
     
  21. Кочергин В. В. Об одном соотношении двух мер сложности вычисления систем одночленов // Вестн. Моск. ун-та. Сер. 1. 2009. № 4. С. 8–13.

Исследование выполнено при финансовой поддержке Министерства науки и высшего образования России в рамках программы Московского центра фундаментальной и прикладной математики (соглашение № 075–15–2025–345). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Корнеев Сергей Александрович
  1. Московский гос. университет им. М. В. Ломоносова, 
    Ленинские горы, 1, 119991 Москва, Россия
  2. Московский центр фундаментальной и прикладной математики, 
    Ленинские горы, 1, 119991 Москва, Россия

E-mail: korneev.sa.42@gmail.com 

Статья поступила 18 июня 2025 г.
После доработки — 20 августа 2025 г.
Принята к публикации 22 сентября 2025 г.

Abstract:

We study circuit complexity of monomial system computation. In the considered computational model, the complexity means the minimal number of composition operations sufficient to compute the monomial system. Multiple use of results in intermediate calculations is allowed. We consider a three-monomial system without zeros. The main results of this paper are as follows. A formula for asymptotic growth of circuit complexity of system computation is established. In case of three variables, a more accurate formula is obtained, which expresses circuit complexity of system computation with precision of one. 

Tab. 1, bibliogr. 21.

References:
  1. A. I. Shirshov, Some algorithmic problems for Lie algebras, Sib. Mat. Zh. 3 (2), 292–296 (1962) [Russian].
     
  2. Yu. V. Merekin, On the generation of words using the composition operation, Diskretn. Anal. Issled. Oper., Ser. 1, 10 (4), 70–78 (2003) [Russian].
     
  3. Yu. V. Merekin, Some bounds on the complexity of words, Southeast Asian Bull. Math. 30 (6), 1081–1121 (2006).
     
  4. E. N. Trusevich, On the complexity of implementation of a system of two monomials in two variables by composition circuits, in Proc. VIII Youth Sci. Sch. Discrete Mathematics and Its Applications, Pt. 2 (Moscow, Russia, Oct. 24–29, 2011) (IPM RAN, Moscow, 2011), pp. 40–44 [Russian].
     
  5. E. N. Trusevich, Complexity of certain systems of monomials in calculation by composition circuits, Vestn. Mosk. Univ., Ser. 1, No. 5, 18–22 (2014) [Russian] [Mosc. Univ. Math. Bull. 69 (5), 193–197 (2014), DOI: 10.3103/ S0027132214050039].
     
  6. S. A. Korneev, On the complexity of implementation of a system of two monomials by composition circuits, Diskretn. Mat. 32 (2), 15–31 (2020) [Russian] [Discrete Math. Appl. 31 (2), 113–125 (2021), DOI: 10.1515/dma-2021-0010].
     
  7. S. A. Korneev, On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials, Uchyon. Zap. Kazan. Univ., Ser. Fiz.-Mat. Nauki 162 (3) 300–310 (2020) [Russian].
     
  8. S. A. Korneev, The complexity of implementation of a system of monomials in two variables by composition circuits, Prikl. Diskretn. Mat., No. 53, 103–119 (2021) [Russian].
     
  9. O. B. Lupanov, Asymptotic Estimates for the Complexity of Control Systems (Izd. Mosk. Univ., Moscow, 2024) [Russian].
     
  10. J. E. Savage, The Complexity of Computing (Wiley, New York, 1976; Faktorial, Moscow, 1998 [Russian]).
     
  11. V. M. Khrapchenko, Lower Bounds for the Complexity of Circuits of Functional Elements, in Cybernetics Collection, New Series, Vol. 21 (Mir, Moscow, 1984), pp. 3–54.
     
  12. V. V. Kochergin, The R. Bellman’s and D. Knuth’s Problems and Their Generalizations: The Complexity of Additive Computing (Palmarium Acad. Publ., Saarbrücken, 2012).
     
  13. V. V. Kochergin, On Bellman’s and Knuth’s problems and their generalizations, Fundam. Prikl. Mat. 20 (6), 159–188 (2015) [Russian] [J. Math. Sci. 233 (1), 103–124 (2018), DOI: 10.1007/s10958-018-3928-4].
     
  14. V. V. Kochergin, The Bellman, Knuth, Lupanov, Pippenger problems and their variations as generalizations of the additive circuits problem, in Mathematical Problems of Cybernetics, Vol. 20 (Fizmatlit, Moscow, 2022), pp. 119–256 [Russian].
     
  15. V. V. Kochergin, On the computation complexity of systems of monomials in two variables, in Proc. VII Int. Conf. “Discrete Models in Control Systems Theory” (Pokrovskoe, Russia, Mar. 4–6, 2006) (MAKS Press, Moscow, 2006), pp. 185–190 [Russian].
     
  16. A. F. Sidorenko, Complexity of additive computations of systems of linear forms, in Zap. Nauchn. Sem. LOMI, Vol. 105. Theoretical Applications of Methods of Mathematical Logics, Pt. III (Nauka, Leningrad, 1981), pp. 53–61 [Russian] [J. Sov. Math. 22 (3), 1310–1315 (1983), DOI: 10.1007/BF01084394].
     
  17. D. E. Knuth and C. H. Papadimitriou, Duality in addition chains, Bull. Eur. Assoc. Theor. Comput. Sci. 13, 2–4 (1981).
     
  18. J. Olivos, On vectorial addition chains, J. Algorithms 2 (1), 13–21 (1981).
     
  19. V. V. Kochergin, On the complexity of joint computing of tree monomials it tree variables, in Mathematical Problems of Cybernetics, Vol. 15 (Fizmatlit, Moscow, 2006), pp. 79–154 [Russian].
     
  20. V. V. Kochergin, A simple proof for the upper bound of the computational complexity of three monomials in three variables, Vestn. Mosk. Univ., Ser. 1, No. 2, 3–8 (2019) [Russian] [Mosc. Univ. Math. Bull. 74 (2), 43–48 (2019), DOI: 10.3103/S0027132219020013].
     
  21. V. V. Kochergin, Relation between two measures of the computation complexity for systems of monomials, Vestn. Mosk. Univ., Ser. 1, No. 4, 8–13 (2009) [Russian] [Mosc. Univ. Math. Bull. 64 (4), 144–149 (2009), DOI: 10.3103/S0027132209040020].