The complexity of the implementation of systems of monomials by composition schemes is investigated. For this computational model, the complexity of the implementation of a system of p monomials in two variables is established up to a term of order p. It is shown that for composition schemes, in contrast to other models, the asymptotic growth of the complexity of the realization of a system of a limited number of monomials in two variables, generally speaking, is not determined by the complexity of any improper subset of monomials.
Download file
Counter downloads: 41
- Title The complexity of implementation of a system of monomials in two variables by composition circuits
- Headline The complexity of implementation of a system of monomials in two variables by composition circuits
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 53
- Date:
- DOI 10.17223/20710410/53/7
Keywords
set of monomials, computation complexity, circuit complexity, composition circuitAuthors
References
Кочергин В. В. О сложности вычислений одночленов и наборов степеней // Тр. Ин-та математики СО РАН. 1994. Т. 27. С. 94-107.
Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней // Методы дискретного анализа в теории графов и сложности. 1992. Вып. 52. С. 22-40.
Yao A. C.-C. On the evaluation of powers // SIAM J. Computing. 1976. V. 5. P. 100-103.
Bellman R. E. Addition chains of vectors (Advanced problems 5125) // Amer. Math. Monthly. 1963. V. 70. P. 765.
Straus E. G. Addition chains of vectors // Amer. Math. Monthly. 1964. V. 71. P. 806-808.
Schonhage A. A lower bound for the lenght of addition chains // Theor. Comput. Sci. 1975. V. 1. P. 1-12.
Кочергин В. В., Кочергин Д. В. Уточнение нижней оценки сложности возведения в степень // Прикладная дискретная математика. 2017. №38. С. 119-132.
Erdos P. Remarks on number theory, III: On addition chains // Acta Arithmetica. 1960. V. 6. P. 77-81.
Brauer A. On addition chains // Bull. AMS. 1939. V. 45. P.736-739.
Кнут Д. Е. Искусство программирования для ЭВМ. Т. 2. М.: Мир, 1977.
Кочергин В. В. О задачах Беллмана и Кнута и их обобщениях // Фундаментальная и прикладная математика. 2015. Т. 20. №6. С. 159-188.
Pippenger N. On the evaluation of powers and monomials // SIAM J. Comput. 1980. V. 9. No. 2. P. 230-250.
Ширшов А. И. Некоторые алгоритмические проблемы для алгебр Ли // Сибирский математический журнал. 1962. Т. 3. С. 292-296.
Корнеев С. А. Об асимптотическом поведении функций шенноновского типа, характеризующих сложность вычисления систем мономов // Ученые записки Казанского университета. Сер. Физико-математические науки. 2020. Т. 162. №3. С. 300-311.
Корнеев С. А. О сложности реализации системы из двух мономов схемами композиции // Дискретная математика. 2020. Т. 32. №2. C. 15-31.
Трусевич Е. Н. О сложности вычисления некоторых систем одночленов схемами композиции // Вестник Московского университета. Сер. 1. Математика. Механика. 2014. №5. С. 18-22.
Мерекин Ю. В. О порождении слов с использованием операции композиции // Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10. №4. С. 70-78.
Кочергин В. В. Уточнение оценок сложности вычисления одночленов и наборов степеней в задачах Беллмана и Кнута // Дискретный анализ и исследование операций. 2014. Т. 21. №6. С. 51-72.
Кочергин В. В. О сложности вычисления систем одночленов от двух переменных // Труды VII Междунар. конф. «Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта 2006). М.: МАКС Пресс, 2006. С. 185-190.
Сидоренко А. Ф. Сложность аддитивных вычислений семейства целочисленных линейных форм // Записки научных семинаров ЛОМИ. Л.: Наука, 1981. Т. 105. С. 53-61.
Кочергин В. В. Об асимптотике сложности аддитивных вычислений систем целочисленных линейных форм // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13. №2. С. 38-58.
Кочергин В. В. О сложности совместного вычисления трех элементов свободной абелевой группы с двумя образующими // Дискретный анализ и исследование операций. Сер. 1. 2008. Т. 15. №2. С. 23-64.
The complexity of implementation of a system of monomials in two variables by composition circuits | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 53. DOI: 10.17223/20710410/53/7
Download full-text version
Counter downloads: 112