ГлавнаяАрхивО сложности реализации системы мономов от двух переменных схемами композиции

О сложности реализации системы мономов от двух переменных схемами композиции | Прикладная дискретная математика. 2021. № 53. DOI: 10.17223/20710410/53/7

Исследуется сложность реализации систем мономов схемами композиции. Для этой вычислительной модели установлена сложность реализации системы из p мономов от двух переменных с точностью до слагаемого порядка р. Показано, что для схем композиции, в отличие от других моделей, асимптотика роста сложности реализации системы из ограниченного числа мономов от двух переменных, вообще говоря, не определяется сложностью никакого несобственного подмножества мономов.
  • Title О сложности реализации системы мономов от двух переменных схемами композиции
  • Headline О сложности реализации системы мономов от двух переменных схемами композиции
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 53
  • Date:
  • DOI 10.17223/20710410/53/7
Ключевые слова
система мономов, сложность вычисления, схемная сложность, схема композиции
Авторы
Ссылки
Кочергин В. В. О сложности вычислений одночленов и наборов степеней // Тр. Ин-та математики СО РАН. 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.
О сложности реализации системы мономов от двух переменных схемами композиции | Прикладная дискретная математика. 2021. № 53. DOI: 10.17223/20710410/53/7
О сложности реализации системы мономов от двух переменных схемами композиции | Прикладная дискретная математика. 2021. № 53. DOI: 10.17223/20710410/53/7