Том 21, номер 6, 2014 г., Стр. 51-72

УДК 519.7
Кочергин В. В.
Уточнение оценок сложности вычисления одночленов и наборов степеней в задачах Беллмана и Кнута

Аннотация:
Изучаются два обобщения классической задачи о наискорейшем возведении в степень — задача Беллмана о сложности (наименьшем числе операций умножения) вычисления исходя только из переменных нормированного одночлена от m переменных и задача Кнута о сложности совместного вычисления системы из m степеней одной переменной. Даётся обзор некоторых результатов, связанных с этими задачами, а также уточняются асимптотические оценки сложности в задачах Беллмана и Кнута, когда поведение величины m сравнимо со сложностью (они имеют одинаковый порядок роста). Помимо того, что установленные верхние и нижние оценки сложности для задач Беллмана и Кнута для почти всех наборов степеней дают асимптотику роста сложности в широком диапазоне соотношений параметров (число переменных или вычисляемых степеней, значение максимального показателя степени и произведение всех показателей степеней), они ещё гарантируют при любом соотношении параметров превышение верхней оценки над нижней асимптотически не более, чем в 5/3 раза.
Библиогр. 25.

Ключевые слова: аддитивная цепочка, вычисление степени, вычисление одночлена, задача Беллмана, задача Кнута.

Кочергин Вадим Васильевич ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 1, 119991 Москва, Россия
е-mail: vvkoch@yandex.ru

Статья поступила 18 февраля 2014 г.
Исправленный вариант — 20 мая 2014 г.

Литература

[1] Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней // Методы дискретного анализа в теории графов и сложности. - Новосибирск, 1992. - Вып. 52. - С. 22–40.

[2] Кнут Д. Е. Искусство программирования для ЭВМ. - М.: Мир, 1977. - T. 2. - 724 c.

[3] Кочергин В. В. О сложности вычислений в конечных абелевых группах // Мат. вопросы кибернетики. - М.: Наука, 1992. - Вып. 4. - С. 178–217.

[4] Кочергин В. В. О сложности вычислений в конечных абелевых группах // Докл. АН СССР. - 1991. - Т. 317, № 2. - С. 291–294.

[5] Кочергин В. В. О вычислении наборов степеней // Дискрет. математика. - Т. 6, вып. 2. - 1994. - С. 129–137.

[6] Кочергин В. В. О сложности вычислений одночленов и наборов степеней // Дискретный анализ. - Новосибирск: Изд-во Института математики СО РАН, 1994. - С. 94–107. (Тр. РАН. Сиб. отд-ние. Ин-т математики; Т. 27)

[7] Кочергин В. В. О двух обобщениях задачи об аддитивных цепочках // Тр. IV Междунар. конф. «Дискретные модели в теории управляющих систем» (Москва, 19–25 июня 2000 г.). - М.: МАКС Пресс, 2000. - С. 55–59.

[8] Кочергин В. В. О сложности вычисления пары одночленов от двух переменных // Дискрет. математика. - Т. 17, вып. 4. - 2005. - С. 116–142.

[9] Кочергин В. В. О сложности вычисления системы из трех одночленов от трех переменных // Мат. вопросы кибернетики. - М.: Наука, 2006. - Вып. 15. - С. 79–155.

[10] Лупанов О. Б. О синтезе некоторых классов управляющих систем // Пробл. кибернетики. - 1963. - Вып. 10. - C. 63–97.

[11] Лупанов О. Б. Об одном подходе к синтезу управляющих систем - принципе локального кодирования // Пробл. кибернетики - 1965. - Вып. 14. - C. 31–110.

[12] Сидоренко А. Ф. Сложность аддитивных вычислений семейств целочисленных линейных форм // Зап. науч. семинаров ЛОМИ. - 1981. - Т. 105. - С. 53–61.

[13] Bellman R. E. Addition chains of vectors (advanced problem 5125) // Amer. Math. Monthly. - 1963. - Vol. 70. - P. 765.

[14] Brauer A. On addition chains // Bull. Amer. Math. Soc. - 1939. - Vol. 45. - P. 736–739.

[15] Downey P., Leong B., Sethi R. Computing sequences with addition chains // SIAM J. Comput. - Vol. 10. - 1981. - P. 638–646.

[16] Erdös P. Remarks on number theory. III: On addition chains // Acta Arith. - 1960. - Vol. 6. - P. 77–81.

[17] Gordon D. M. A survey of fast exponentiation methods // J. Algorithms. - 1998. - Vol. 27. - P. 129–146.

[18] Knuth D. E., Papadimitriou C. H. Duality in addition chains // Bull. Eur. Assoc. Theor. Comput. Sci. - 1981. - Vol. 13. - P. 2–4.

[19] Olivos J. On vectorial addition chains // J. Algorithms. - 1981. - Vol. 2, N 1. - P. 13–21.

[20] Pippenger N. On evaluation of powers and related problems // Proc. 17th Ann. IEEE Symp. Found. Comput. Sci. (Houston, TX, 25–27 Oct. 1976). - P. 258–263.

[21] Pippenger N. On evaluation of powers and monomials // SIAM J. Comput. - 1980. - Vol. 9, N 2. - P. 230–250.

[22] Southard T. H. Addition chains for the first N squares // Tech. Rep. CNA-84, Univ. Texas, Austin, 1974.

[23] Straus E. G. Addition chains of vectors // Amer. Math. Monthly. - 1964. - Vol. 71. - P. 806–808.

[24] Subbarao M. V. Addition chains - some results and problems // Number Theory and Applications. NATO Adv. Sci. Inst. Ser.: Ser. C. - Kluwer Acad. Publ. Group, 1989. - Vol. 265. - P. 555–574.

[25] Yao A. C.-C. On the evaluation of powers // SIAM J. Comput. - 1976. - Vol. 5. - P. 100–103.