О сложности аддитивных вычислений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.7

Кочергин Вадим Васильевич О СЛОЖНОСТИ АДДИТИВНЫХ ВЫЧИСЛЕНИЙ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва 2008

Работа выполнена на кафедре дискретной математики Механико-матемаг тического факультета Московского государственного университета имени М. В. Ломоносова.

Официальные оппоненты: доктор физико-математических наук,

профессор Глухов Михаил Михайлович

доктор физико-математических наук, профессор Шевченко Валерий Николаевич

доктор физико-математических наук, профессор Шоломов Лев Абрамович

Ведущая организация: Институт математики им. С. Л. Соболева

Сибирского отделения РАН

Защита диссертации состоится 17 октября 2008 г. в 16 часов 45 минут на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, ГСП-1, Москва, Ленинские горы, д. 1, МГУ имени М. В. Ломоносова, Механика-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М. В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 17 сентября 2008 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

-------общая|характеристика работы

Актуальность темы. Данная работа относится к одной из центральных областей дискретной математики и математической кибернетики — теории синтеза и сложности управляющих систем, получающей постановки задач и находящей многообразные применения в информатике и вычислительной технике.

Проблему синтеза управляющих систем кратко можно сформулировать следующим образом. Задан запас элементов (базис), реализующих некоторые функции. Заданы правила построения из элементов более сложных объектов — схем, а также задан способ нахождения по схеме реализуемой (вычисляемой) ею функции; схема определяет строение, а функция — поведение управляющей системы или модели вычислений. Задача состоит в построении для каждой рассматриваемой функции схемы, которая реализует эту функцию, причем обычно важно не просто построить схему, но и добиться, чтобы она была в каком-то определенном смысле наилучшей. Качество схемы обычно выражается с помощью какой-либо из мер сложности, среди которых рассматриваются, в частности1), число элементов, стоимость, занимаемые объем или площадь, глубина, задержка, мощность и др.

Если базис является конечным, то существует тривиальный переборный алгоритм решения этой задачи. Однако реально воспользоваться им чаще всего невозможно, так как с ростом числа элементов в схемах количество схем растет очень быстро и применение тривиального метода становится практически неосуществимым. На самом деле большая трудоемкость решения задачи синтеза в общем виде присуща всем алгоритмам, предназначенным для ее решения, — к этому выводу одним из первых пришел С. В. Яблонский2). С тех пор эта точка зрения стала общепринятой,

См., например: Лупанов О. Б. Асимптотические оценки, сложности управляющих систем. — М.: Изд-во Московского университета, 1984; Коршунов А. Д. Об оценках сложности схем из объемных функциональных элементов // Проблемы кибернетики, вып. 19. — М.: Наука, 1967. — С. 275-284; Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики, вып. 19. — М.: Наука, 1967. — С. 285-292; Мс-Coll W. F., Paterson М. S. The depth of all Boolean functions // SI AM J. Comput. — 1977. — V. 6, № 2. — P. 373-380; Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23. — М.: Наука, 1970. — С. 43-81; Вайн-цвайг М. Н. О мощности схем из функциональных элементов // Доклады АН СССР. — 1961. — Т. 139, № 2. — С. 320-323; Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов // Проблемы кибернетики, вып. 38. — М.: Наука, 1981. — С. 117-179.

2) Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контакт-

получив много косвенных подтверждений своей справедливости. В силу этого обычно рассматривают некоторые ослабления рассматриваемой задачи. Одно из таких ослаблений заключается в приближенном решении задачи, т. е. в построении не обязательно минимальных, а «достаточно экономных» схем. Но и эта задача при поиске «достаточно точного» решения, вообще говоря, остается очень трудной. Поэтому часто рассматривают задачу построения асимптотически оптимальных схем. Постановка этой задачи, скажем, для классического случая вычисления булевых функций такова. Каждой схеме S ставится в соответствие неотрицательное число L(S) — сложность схемы S, например, число элементов схемы. Считается, что схема тем лучше, чем меньше величина L(S). Через L(j) обозначается сложность схемы из заданного класса, которая реализует / и имеет минимальную сложность. Вводится функция L(n) = maxL(/), где максимум берется по всем рассматриваемым функциям от п переменных. Требуется найти метод синтеза схем, позволяющий для любой рассматриваемой функции / от л переменных стоить схему, которая реализует / и имеет сложность, не превосходящую или мало превосходящую величину L(n). Такой подход был предложен К. Шенноном3) в 1949 г. при исследовании контактных схем и может быть перенесен на другие классы управляющих систем. Функцию L(n) принято называть функцией Шеннона.

Фундаментальные основы асимптотической теории синтеза и сложности управляющих систем были заложены О. Б. Лупановым. Им были предложены асимптотически оптимальные методы синтеза и получены асимптотически точные оценки сложности для важнейших классов управляющих систем — вентильных схем глубины 2, контактно-вентильных схем, схем из функциональных элементов, контактных схем, схем из функциональных элементов без ветвления выходов (формул) и с ограниченным ветвлением (формул с частичной памятью), формул ограниченной глубины, параллельно-последовательных контактных схем, релейно-контактных схем и др. При изучении этих модельных классов управляющих систем О. Б. Лупановым были выявлены новые эффекты и закономерности, в числе которых было явление, названное эффектом Шеннона: при реализации в большинстве исследованных им классов управляющих систем почти все функции имеют почти одинаковую сложность, асимптотически равную сложности наиболее сложных функций.

К асимптотической теории синтеза и сложности управляющих систем

ных схем // Проблемы кибернетики, вып. 2. — М.: Физматгиз, 1959. — С. 75-121.

3) Shannon С. Е. The synthesis of two-terminal switching circuits // Bell Syst. Techn. J. — 1949. — V. 28, № 1. — P. 59-98.

относятся и вопросы, исследуемые в данной работе. При этом часть изучаемых вопросов следует отнести к области построения универсальных методов синтеза (расчитанных на реализацию произвольных функций), а другую — к области синтеза схем для конкретных (индивидуальных) функций (последовательностей функций).

Рассматриваемые в работе вычислительные схемы относятся к одному из важнейших модельных классов управляющих систем — классу схем из функциональных элементов. При этом изучаемые схемы обладают также многими свойствами, присущими вентильным схемам — классу наиболее простых управляющих систем, несущему большую «топологическую» нагрузку и удобному для разработки общих методов синтеза, которые, как правило, в той или иной степени могут быть промоделированы в других классах управляющих систем.

В работе изучаются различные обобщения хорошо известной задачи о сложности возведения в степень, т. е. задачи о нахождении величины 1(хп) — минимального числа операций умножения, достаточного для вычисления по переменной х величины хп. Эту задачу (а также ее обобщения) обычно рассматривают в аддитивной постановке — это известная задача об аддитивных цепочках, которая формулируется следующим образом4). Аддитивной цепочкой для натурального числа п называется всякая последовательность целых чисел

а0 = 1, ох,..., ат = п,

удовлетворяющая следующему свойству: для каждого k, 1 < к < тп, найдется два целых числа (не обязательно различных) i и j, 0 < г, j < к — 1, таких, что aie = а< + a j. Минимальная длина тп аддитивной цепочки для п называется аддитивной сложностью числа п и обозначается 1{п). Очевидно, что величины 1{п) и 1(хп) совпадают.

Считается, что задачу определения величины 1{п) поставил в 1894 г. X. Деллак, хотя, по-видимому, еще в древней Индии был известен «бинарный» метод возведения в степень. В 1937 г. А. Шольц для этой задачи ввел понятие аддитивной цепочки.

В 1939 А. Брауэром5) для величины 1(п) при п —>■ оо была установлена

4) Кнут Д. Е. Искусство программирования, т. 2. 3-е издание. — М.: Издательский дом «Вильяме», 2000.

5) Brauer A. On addition chains // Bull. Amer. Math. Soc. — 1939. — V. 45. — P. 736739.

асимптотическая формула6)

1(п) ~ logn,

причем им была получена верхняя оценка

В 1960 г. П. Эрдёш7) показал, что для почти всех п справедливо асимптотическое равенство

log log п

logn

при этом стоит отметить разную природу слагаемых в правой части этого равенства — слагаемое log п связано с величиной числа п и должно присутствовать для любого значения п, а «мощностное» слагаемое (отношение логарифма количества чисел, не превосходящих п, к повторному логарифму) зависит от «строения» числа п и присутствует для «почти всех» п.

После этого исследовались (как правило, на языке аддитивных цепочек) различные вопросы, связанные с задачей о наискорейшем возведении в степень8).

Теперь перейдем к обобщениям задачи об аддитивной сложности натурального числа (или задачи о наискорейшем возведении в степень). Эти обобщения, по-существу, являются основными объектами исследования данной работы.

Пусть А = (aij) — целочисленная матрица размера р х q с неотрицательными коэффициентами без нулевых строк.

Аддитивной цепочкой для матрицы А называется9) последователь-

6) Здесь и далее logx означает log2x, а запись f(n) ~ д(п) означает, что при п —> оо отношение f(n)/g(п) стремится к 1.

7) Erdos P. Remarks on number theory, III: On addition chains // Acta Arith. — 1960. — V. 6. — P. 77-81.

8) См., например, обзоры: Subbarao M. V. Addition chains — some results and problems // Number Theory and Applications. Editor R. A. Mollin. NATO Advanced Science Institutes Series: Series C. — Kluwer Academic Publisher Group, 1989. — V. 265. — P. 555-574; Bos J., Coster M. Addition chain heuristics // Proceedings of Crypto'&9. — Springer-Verlag, 1990. — V. 435. — P. 400-407; Gordon D. M. A survey of fast exponentiation methods // Journal of Algorithms. — 1998. — V. 27. — P. 129-146.

9) Knuth D. E., Papadimitriou С. H. Duality in addition chains // Bulletin of the European association for Theoretical Computer Science. — 1981. — V. 13. — P. 2-4.

ность g-мерных векторов (наборов) вида

Vl = (1,0,..., 0), V2 = (0,1,..., 0),..., v, = (0,0,..., 1),

V9+l,V9+2, . . . ,v,+r,

начинающаяся с q единичных векторов и удовлетворяющая условиям:

1) для каждого к, q + l<k<q + r, найдется два натуральных числа (не обязательно различных) imj,l<i<k — 1, 1 < j < к — 1, таких, что vfc = Vj + Vj (сложение векторов покомпонентное);

2) {(an, <И2, • • ■ <*!,), (o2i,a22, • • - Яг?), • • ■, (aPi,aP2>. ■ .ap,)} Q

С {vbv2,...,vi+r}.

Число г называется длиной цепочки. Минимальная длина аддитивной цепочки для матрицы А называется аддитивной сложностью (вычисления, порождения, реализации) матрицы А и обозначается через 1(А).

Задача об аддитивной сложности матриц по-существу совпадает с известной10) задачей о сложности вычисления систем одночленов (систем коммутативных мономов) — величина 1(А) численно равна минимально возможному числу операций умножения, достаточному для (схемного) вычисления по переменным Xj, х2, ■ ■ ■, xq задаваемой матрицей А системы одночленов

fi =a:;i,as;u...®;,*l /2 = • • ■ ■■■, /Р = ... х^',

(при этом допускается многократное использование промежуточных результатов).

Пусть теперь А — (a<j) — произвольная (не обязательно с неотрицательными элементами и без нулевых строк) целочисленная матрица. Определим еще две меры сложности порождения таких матриц.

Через h(A) обозначим минимальную длину обобщенных аддитивных цепочек для матрицы А, в которых помимо операции сложения (v* = Vi 4- Vj) разрешена и операция вычитания (vjt = v< — Vj). Величина /г(-А) численно равна минимально возможному числу операций умножения и деления, достаточному для (схемного) вычисления по переменным х\, х2,. ■., xq задаваемой матрицей А системы функций = х"'1!^'2 • • ■

10) См., например: Pippenger N. Он evaluation of powers and monomials // SIAM J. Comput. — 1980. — V. 9, N 2. — P. 230-250; Vassiliev N. N. Complexity of monomial evaluations and duality // Computer algebra in scientific Computing — CASC99 {Munich). — Berlin: Springer, 1999. — P. 479-484; Bernstein D. J. Pippenger's exponentiation algo-rithm//Available at: http://cr.yp.to/papers/pippenger.pdf. — 2002.

i = 1,2а также минимально возможному числу операций сложения и вычитания, достаточному для (схемного) вычисления по переменным х\,х2, ■ ■ ■ ,хд задаваемой матрицей А системы целочисленных линейных форм gi = ацХ1 + ai2x2 +... + aiqxq, i = 1,2,..., р. В таком виде задача о нахождении величины h{A) поставлена, например, А. Ф. Сидоренко11).

Эта мера сложности тесно связана с быстрыми вычислениями на эллиптических кривых12) и имеет два малоотличающихся друг от друга варианта — не допускающий13) операции вида Vj. = —Vj — Vj и допускающий14) такие операции.

Через If(A) обозначим минимальную длину таких аддитивных цепочек для матрицы .А, в которых используется только операции сложения (у* = Vi + Vj), но которые начинаются не с g начальных единичных векторов," а с 2q векторов — помимо векторов vi, v2,..., vg разрешается использовать противоположные к ним векторы — Vi, —v2,..., —v5. Величина If{A) численно равна минимально возможному числу операций умножения, достаточному для (схемного) вычисления по образующим х\, х2,..., хч свободной абелевой группы и обратным к ним элементам х^"1, х^1,..., i"1 задаваемой матрицей А системы /,• = х^х^2 ■. ■ Хд'", г — 1, 2,... элементов этой группы. Впервые, по-видимому, такая мера сложности исследовалась Ф. Штрассеном15) (причем не только для коммутативного случая).

Величины 1(A), h(A) и If{A) можно интерпретировать как минимально возможную сложность (число элементов) схемы из функциональных элементов16), на входы которой подаются переменные xlt х2, ■ ■ ■, хя (а также

п) Сидоренко А. Ф. Сложность аддитивных вычислений семейств целочисленных линейных форы // Записки научных семинаров ЛОМИ. -— JI.: Наука, 1981. — Т. 105. — С. 53-61.

12) Morain F., Olivos J. Speeding up the computation on an eliptic curve using addition-subsraction chains // Informatique Théorique et Applications. — 1990. — V. 24. — P. 531 544.

13) См., например: Volger H. Some results on addition/subtraction chains // Information Processing Letters. — 1985. — V. 20. — P. 155-160; Goundar R. R., Shiota K., Toyonaga M. New strategy for doubling-free short addition-subtraction chain // International Journal of Applied Mathematics. — 2007. — V. 2, № 3.

14) См., например: Kunihiro N., Yamamoto H. Window and extended window methods for addition chain and addition-subtraction chain // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 1998. — V. E81-A, № 1. — P. 72-81; Kweon K., Hong S.-M., Oh S.-Y., Yoon H. Finding shorter addition/subtraction-chains // CCCT'05 (International Conference on Computing, Communications and Control Technologies). — http://hdl.handle.net/10203/447

1Б) Strassen V. Berechnungen in partiellen Algebren endlichen Typs // Computing. — 1973.— V. 11, — P. 181-196.

16) См., например: Лупанов О. Б. О синтезе некоторых классов управляющих си-

обратные к ним величины xj"1, xj1,..., х"1, если речь идет о мере сложности If), на выходах схемы вычисляются функции Л, /2, ■ • •, /Р, задаваемые матрицей А, а сама схема состоит из двухвходовых элементов, реализующих произведение (произведение или частное, если речь идет о мере сложности ¿2) функций, подаваемых на входы элемента.

В 1963 г. Р. Беллман17), а затем в 1964 г. Е. Страус18) сформулировали задачу о сложности вычисления одночлена от q переменных (в наших обозначениях — случай р = 1, мера сложности — I), т. е. нахождения величины 1{х11х22 ■ ■

В 1969 г. Д. Кнут19) поставил задачу о сложности вычисления р степеней одной переменной (в наших обозначениях — случал q = 1, мера сложности — I), т. е. нахождения величины 1(ха1,хаг,..., ха").

Е. Страус показал, что для любого фиксированного q при ^ а< —> оо справедлива асимптотическая формула

¿(x^xíj2 • • • я,') ~ log(maxa¿).

А. Яо20) установил аналогичную формулу для любого фиксированного р при at —> 00:

1{ха\ха\...,ха>) ~log(maxa¿).

В 1981 г. независимо А. Ф. Сидоренко, Дж. Оливосом21), а также Д. Кнутом и К. Пападимитриу было доказано, что в действительности задачи о сложности вычисления одночлена от m переменных и набора m степеней эквивалентны (и, следовательно, достаточно исследовать одну из них). На самом деле было установлено более сильное утверждение о двойственности относительно меры сложности I: сложность системы одночленов {/i, /2,..., fp} от q переменных, заданной матрицей А = (а^) размера р x q и сложность двойственной системы одночленов {/i, /2, • ■ ■, fq} от р переменных, заданной транспонированной матрицей Ат = (a,ji) размера

стем // Проблемы кибернетики, вып. 10. — М.: Физматгиэ, 1963. — С. 63-97; Сэвидж Д. Е. Сложность вычислений. — М.: Изд.-во «Факториал». — 1998.

17) Bellman R. Е. Addition chains of vectors (Advanced problem 5125) // Amer. Math. Monthly. — 1963. — V. 70. — P. 765.

18) Straus E. G. Addition chains of vectors // Ame г. Math. Monthly. — 1964. — V. 71. — P. 806-808.

19) Кнут Д. E. Искусство программирования для ЭВМ, т. 2. 1-е издание. — М.: Мир, 1977. — Разд. 4.6.3, упр. 32.

20) Yao А. С.-С. On the evaluation of powers // SI A M J. Comput. — 1976. — V. 5. — P. 100-103.

21) Olivos J. On vectorial addition chains // J. Algorithms. — 1981. — V. 2, N 1. — P. 13-21.

q x p, для любой матрицы А без нулевых строк и столбцов связаны соотношением

1(/ь Л, • ■ • , fp) + Р = l(L к ■ ■ ■ , fg) + <7,

т. е. для любой целочисленной матрицы А с неотрицательными элементами размера р х q без нулевых строк и столбцов выполняется равенство

1{А) + р = I (Ат) + q.

Похожее соотношение для двух матриц, получающихся друг из друга путем транспонирования, справедливо и для меры сложности ¿2-

Также в 1981 г- установлено22), что задача распознавания по набору натуральных чисел (ni,n2,-... , пр,/) существования аддитивной цепочки, имеющей длину I и содержащей числа ni, п2,..., пр, является iVP-полной. В связи с этим дополнительный вес приобретает асимптотическая постам новка исходной задачи. Требуется найти метод построения для матрицы А аддитивной цепочки (соответствующего типа), длина которой в том или ином смысле близка к значению 1(A), h{A) или If(A) соответственно. Например, такой метод, чтобы отношение длины построенной цепочки для матрицы А = (ay) к значению соответствующей меры сложности матрицы стремилось к 1 при ^ |ау| —> оо для всех или «почти всех» матриц.

Существенным продвижением в этом направлении стала работа Н. Пиппенджера23). В ней исследовано асимптотическое поведение функции Шеннона, характеризующей сложность «самой сложной» матрицы среди матриц заданного размера с элементами, не превосходящими заданного значения К — 1, и определяемой при К > 2 равенством L(p,q,K) — maxi (Л), где максимум берется по всем целочисленным матрицам А = (a,ij) с неотрицательными элементами без нулевых строк размера р х q, удовлетворяющим условиям a<j < К — 1, г = 1,..., р, j = 1,..., q. С использованием своего технически весьма громоздкого и существенно опирающегося на результаты О. Б. Лупанова24) и Э. И. Нечипорука25) способа26) построения асимптотически оптимальных обобщенных вентильных схем,

22) Downey P., Leong В., Sethi R. Computing sequences with addition chains // SIAM Journal on Computing. — V. 10. — 1981. — P. 638-646.

23) Pippenger N. On evaluation of powers and monomials // SIAM J. Comput. — 1980. — V. 9, N 2. — P. 230-250.

24) Лупанов О. Б. О вентильных и контактно-вентильных схемах // Доклады АН СССР. — 1956. — Т. 111, N» 6. — С. 1171-1174.

25) Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики, вып. 21. — М.: Наука, 1969. — С. 5-102.

2в) Pippenger N. The mimimum number of edges in graphs with prescribed paths // Math. Systems Theory. — 1979. — V. 12, № 4. — P. 325-346.

реализующих целочисленные матрицы с неотрицательными элементами, Пиппенджер показал, что при условии pq log К —> оо имеет место асимптотическое равенство

L(p, q, К) = min(р, q) log К+

Однако для конкретных (индивидуальных) матриц (последовательностей матриц) никаких нетривиальных асимптотически точных оценок сложности, кроме случая р = 1 при фиксированном q или 9 = 1 при фиксированном р, ни для одной из определенных здесь мер сложности известно, по-видимому, не было.

Цель работы. Целью диссертационной работы является исследование асимптотических закономерностей поведения величин 1(A), Ь(А) и ljr(A) при различных ограничениях на размеры и величину элементов целочисленных матриц А, построение асимптотически оптимальных методов вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободной абелевой группы, поиск и изучение новых эффектов и закономерностей в этой области.

Методы исследования. При решении рассматриваемых задач использовались методы дискретной математики и математической кибернетики.

Научная новизна. Все основные результаты диссертации являются новыми. Основные положения, выносимые на за,щиту, следующие:

• Для задачи о сложности вычисления одночлена от нескольких переменных (задача Беллмана) и для задачи о сложности вычисления набора степеней одной переменной (задача Кнута) при слабых ограничениях в области изменения параметров получены асимптотически точные решения.

• Установлена общая нижняя оценка сложности вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободных абелевых групп.

• Предложен метод получения верхних оценок сложности систем одночленов, основанный на использовании усиленной модели вычислений

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

• Для любых фиксированных (или слаборастущих) значениях р и д установлена асимптотика роста сложности вычисления системы из р целочисленных линейных форм от <7 переменных.

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

• С использованием полученных оценок сложности вычисления наборов степеней установлена асимптотика роста сложности вычисления двоичных слов с заданным числом (или долей) единиц схемами конкатенации.

• Выявлены новые эффекты в задачах о сложности вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободных абелевых групп; в частности, установлены принципиальные различия в асимптотическом поведении трех исследуемых мер сложности.

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы при исследовании различных вопросов теории сложности. Некоторые разделы диссертации могут быть использованы в специальных курсах для студентов и аспирантов, обучающихся по специальности математика.

Апробация работы. Научные результаты и положения диссертационной работы докладывались и обсуждались на следующих научных конференциях, семинарах и школах-семинарах: серии всесоюзных (затем международных) конференций «Проблемы теоретической кибернетики» — Волгоград (1990), Саратов (1993), Ульяновск (1996), Нижний Новгород (1999), Казань (2002), Пенза (2005), Казань (2008, пленарный доклад); серии международных семинаров «Дискретная математика и ее приложения» — Москва, МГУ (1993,1995,1998, 2004, 2007); серии всесоюзных (впоследствии международных) школ-семинаров «Синтез и сложность управляющих систем» — Ташкент (1990), Нижний Новгород (1992, 1994, 1996,

1998, 2000), Минск (1993, 1995, 1999), Санкт-Петербург (2006, пленарный доклад); серии международных конференций «Дискретные модели в теории управляющих систем» (1997, 1998, 2000, 2006); а также на совместном французско-российском семинаре «Combinatorial and algorithmical properties of discrete structures» (1999), на международной школе-семинаре «Сложность булевых функций» (Казань, 1999). Большинство из этих докладов нашли отражение в трудах, материалах, тезисах или аннотациях докладов соответствующих конференций и семинаров. Основные результаты диссертации многократно докладывались в МГУ имени М. В. Ломоносова на научно-исследовательских семинарах «Математические вопросы кибернетики» (руководители — С. В. Яблонский; О. Б. Лупанов; О. М. Касим-Заде), «Синтез управляющих систем» (руководители — О. Б. Лупанов; О. М. Касим-Заде), «Синтез управляющих систем и смежные вопросы» (руководители — О. Б. Лупанов и В. М. Храпченко) и других, а также на Ломоносовских чтениях в МГУ.

Публикации. Основное содержание диссертации опубликовано в 24 работах автора, список которых приведен в конце автореферата [1-24].

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав и списка использованной литературы из 151 наименования. Полный объем работы составляет 344 страницы. Работа содержит 21 рисунок. Нумерация теорем, лемм, утверждений, следствий, замечаний и формул — двойная, состоящая из номера главы и собственно номера внутри данной главы.

основное содержание работы

Во введении дается общая характеристика работы и краткое содержание глав работы.

В главе 1 исследуются задача о сложности вычисления одночлена от многих переменных (задача Беллмана) и задача о сложности вычисления системы степеней одной переменной (задача Кнута).

В § 1.1 сначала даются строгие определения уже обсуждавшимся выше трем обобщениям понятия аддитивной сложности натурального числа, с единых позиций вводятся три вычислительные модели и соответствующие им три меры аддитвной сложности целочисленных матриц (1, 12 и If). Соответствующие этим вычислительным моделям и мерам сложности задачи, имеющие единую аддитивную природу, в силу ряда факторов получили условные названия «Вычисление системы одночленов», «Вычисление системы целочисленных линейных форм» и «Вычисление системы элементов свободной абелевой группы».

В асимптотической постановке они формулируются следующим образом. Пусть дана последовательность {Л(п) = (а^(п))} целочисленных матриц (для первой модели эти матрицы должны быть с неотрицательными элементами и без нулевых строк) размера р(п) х д(п), удовлетворяющая при п —► оо условию 1аи1 ~* 00■ Задача состоит в нахождении при

п —> оо асимптотики роста функционала сложности 1(А(п)), 12(А(п)) или 1р(А(п)) соответственно.

Далее изучаются простейшие свойства и соотношения введенных мер сложности, обсуждаются задачи Беллмана и Кнута, получившие усилиями Е. Страуса и А. Яо при фиксированном числе переменных (степеней) асимптотически точное решение. Вопрос об асимптотике роста сложности в случае растущего числа переменных (степеней) оставался открытым.

Из разных соображений, в том числе и основываясь на уже известных результатах, логично предположить, что на сложность вычисления одночлена от нескольких переменных (или системы из нескольких степеней одной переменной) так или иначе оказывают влияние следующие параметры — максимальное значение среди показателей степеней, общее число переменных (или степеней), а также параметр, связанный с общим числом объектов из рассматриваемого класса, и который для изучаемых задач естественно определить как произведение показателей степеней. Каждый из этих параметров, имеющих разную природу, при соответствующих условиях может быть определяющим. Изучению влияния каждого из этих параметров, а также нахождению асимптотики роста сложности в рассматриваемых задачах при слабых ограничениях на соотношения параметров посвящены следующие два параграфа.

В § 1.2 доказываются верхние оценки для задач Беллмана и Кнута. В силу двойственности этих задач достаточно исследовать одну из них. Ключевую роль при этом исследовании играет получение асимптотически наилучшей верхней оценки сложности вычисления одночлена в случае, когда доминирующей является «мощностная» составляющая.

В основе доказательства такой оценки лежит сведение задачи Беллмана к задаче реализации булевых матриц специального вида вентильными схемами — ориентированными графами без ориентированных циклов с двумя группами выделенных вершин, называемых соответственно входами и выходами схемы, такими что ориентированные пути от входа к входу, от выхода к выходу и от выхода к входу отсутствуют, а число путей от 1-го входа к j-uy выходу равно элементу матрицы, стоящему на пересечении г-й строки и j-гo столбца. Вычисляемому одночлену сопоставляется булева матрица, столбцами которой являются двоичные записи показателей

степеней переменных, дополняемые нулями в старших разрядах для выравнивания высоты. С использованием вентильной конструкции27) автора (не вошедшей в данную работу), опирающейся в свою очередь на конструкции О. Б. Лупанова, Э. И. Нечипорука и Н. Пиппенджера и дающей асимптотически оптимальную оценку через «информационную площадь» матрицы, доказывается следующая

Теорема 1.1. Пусть n(s) = (n^fc), n2(s),..., nm(s)(s)), s = 1,2,..., — последовательность наборов натуральных чисел, удовлетворяющая условию n«(s) ~~► 00 • Тогда

+ 0(т + log maxTii),

где N = П\П2 • •. пт.

Это утверждение усиливает следующая теорема, доказанная автором совместно с С. Б. Гашковым28) (на защиту не выносится и включена в работу для полноты изложения):

Теорема 1.2. Для любой последовательности наборов натуральных чисел n(s) = (ni(s), 712(5),..., n„(3)(s)), s — 1,2,..., удовлетворяющей условию —► 00, выполняется неравенство

... х< logmaxni-l-

где N = П\П2 ■ ■ ■ пт.

Заключительная теорема этого параграфа устанавливает асимптотически точную верхнюю оценку при наиболее слабых ограничениях (при этом происходит огрубление оценок остаточных членов), а также дает хорошую верхнюю оценку в случае, когда число переменных в одночлене велико. Она формулируется отдельно для задач Беллмана и Кнута, поскольку в отличие от предыдущих теорем доказываемые оценки для этих задач уже отличаются.

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

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

Теорема 1.3. Пусть функция f(x) при х —> оо удовлетворяет условиям f(x) —»• оо, log/(x) = o(logx). Тогда для любой последовательности наборов натуральных чисел ñ(s) = (n^s), n2(s),..., nm(3)(s)), s = 1,2,..., удовлетворяющей условию nÁs) °°> выполняются неравенства

1{х?х? ... С) < Мтах1ч)(1 + o(l)) + ¿j^v U + o(l))+

m

+ S (Г108("/(/(т))») ~ lo8<m/(/(m))*) П0 -

¿=1

í(x"\ x"2,..., < log (max n¿)(l + o(l)) + (1 + o(l))+

ТП

+ S ([l0g(m/(/(m))2) "i] - log(m/(/(m))2) П.) - 771, ¿=1

где N — П\П2 ■ ■ ■ nm.

В силу неравенства [i] — х < 1 непосредственным следствием теоремы 1.3 являются асимптотические неравенства29)

? ■ • • С) < log(maxrij) + J^L + m,

loeN

l(xn\xn2,...,xnm) <log(maxn¿)+ 6

log log iV

В § 1.3 доказываются нижние оценки для задач Беллмана и Кнута, причем в более сильной второй вычислительной модели, использующей не одну, а две операции. Нижние оценки для меры сложности ¿2 автоматически являются нижними оценками для меры сложности I.

Для исследуемых задач получилось «объединить» в одном утверждении тривиальную нижнюю оценку вида ¡(х^х^2... xj,"1) > log(maxnj) + m — 1 и нижнюю оценку, получающуюся из стандартных мощностных рассуждений30). Впервые «объединить» тривиальную и «мощностную» нижние оценки удалось, по-видимому, П. Эрдешу для задачи о длине аддитивной цепочки для числа п. Развитие эти методы получили в работе Н. Пиппен-джера при оценке снизу сложности вычисления «самой сложной» системы

2в) Здесь и далее запись д(х) < h(x) означает неравенство д(х) < h(x)(l + о(1)).

30) Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики, вып. 14. — М.: Наука, 1965. — С. 31-110.

из р одночленов от q переменных. Здесь при доказательстве нижней оценки описанного вида использованы некоторые основные идеи упомянутых работ.

Для произвольного набора п — (щ, п2,..., пт) различных натуральных чисел через а обозначим перестановку, упорядочивающую набор п по возрастанию: па(1) < пст(2) < ... < пст(т). Положим

2Л(п) = {{кг,к2,...,кт) |

кг < к2 < ... < кт, к{ € N. 1 < к{ < п^), г = 1,2,... ,т).

Теорема 1.6. Пусть последовательность наборов

п(я) = (711(5), п2(в),..., птМ(в)) , 5 = 1,2,...

различных натуральных чисел удовлетворяет условию N(3) = —> оо при 5 —> оо. Тогда существуют такие положительные константы с, с2 и функции /(х) и /2(1), стремящиеся к 0 при х —>■ оо, что доли наборов к2,..., кт) из 971 (п(в)), удовлетворяющих, соответственно, соотношениям

I (х'\ х1", ...,**-)- (logmaxiij 4-ь (ll''xh.....**•)- (bgmaxn, + ¡¿J^)

стремятся к единице при s —► 00.

Утверждение теоремы 1.6 остается справедливым, если рассматривать доли наборов не из множества 97t (n(s)), а из множества 9I(n(s)), где 9t = {(ki,k2,..., кт) | ki G N, 1 < ki г = 1, 2,..., m}. Такой под-

ход является более логичным при изучении задачи Беллмана. Отличия в подходах связаны с соображениями следущего толка — при вычислениях одночлены х"1!^2 и ХТХ21 естественно считать разными, а наборы степеней (х"1, х"2) и (хПа, х"1) — одинаковыми. Стоит отметить, что в изначальной формулировке теоремы 1.6 результат в некотором смысле является более тонким.

Содержательно утверждение теоремы 1.6 означает относительно, скажем, меры сложности I, что при выполнении условий теоремы и, кроме того, условия т = о ^log (maxj ni) + l0gf0^v) ■ для п°чти всех наборов из 971 (п) (или из (п)) справедливо асимптотическое равенство

logiV

I (xfcl, х*\..., xfcm) ~ log (тахп<) +

log log N'

из которого в силу теоремы 1.3 при тех же условиях следует для почти всех наборов и выполнение соотношения

ь %К

l(xkl,xk2,...,xkm) ~ log (maxfci) +

log log К' где К = kik2 - ..km.

При выполнении условия тп > min ^log (maxn,), j утверждения

теорем 1.3, 1.4 и 1.6 дают верхние и нижние асимптотические оценки для задач Беллмана и Кнута, отличающиеся на величину, не превосходящую тп, причем при некоторых дополнительных ограничениях эти утверждения дают асимптотически совпадающие оценки. Простейшим примером асимптотического совпадения оценок является задача вычисления, скажем, одночлена х"1 х£2... х£,т, где щ = о(т2), i = 1,2, ...,m, и все Tij различны. В этом случае указанные оценки устанавливают следующую асимптотику роста сложности: I (х"1^2... ~ 2т.

В § 1.4 рассматривается применение оценок сложности, полученных при исследовании задачи Кнута, для получения асимптотически окончательного результата в одной задаче, которую также можно считать прямым обобщением классической задачи об аддитивных цепочках.

Конкатенацией слов <5 и ß конечной длины над произвольным алфавитом называется слово äß, полученнное приписыванием к слову ä справа слова ß.

Последовательность S слов (наборов) ть т2, ..., fr = ä из конечного алфавита 21 называется схемой конкатенации31), реализующей (вычисляющей) слово (набор) а, если для каждого г, г = 1, 2,..., г, слово Т{ можно представить в виде fj = ß^ß^, где для j = 1,2 либо ß^ — буква из алфавита 01, либо ßij — тт для некоторого ш, удовлетворяющего условию т < г — 1. Сложностью lc(S) схемы конкатенации S называется число г. Положим lc(öt) = min /C(S), где минимум берется по всем схемам конкатенации, реализующим слово ä в алфавите 01. Величина lc{ä) называется мультипликативной сложностью слова (другие названия — аддитивная сложность32), длина цепочек слов33)). В работе исследуются схемы конкатенации в двоичном алфавите, т. е. 01 = {0, 1}.

31) Мерекин Ю. В. Нижняя оценка сложности для схем конкатенации слов // Дискретный анализ и исследование операций. — 1996. — Т. 3, № 1. — С. 52-56.

зг) См., например: Потапов В. Н. Аддитивная сложность слов с ограничениями на состав подслов // Дискретный анализ и исследование операций. Сер. 1. — 2004. — Т. 11, № 1. — С. 52-78; Мерекин Ю. В. Об аддитивной сложности частично коммутативных слов // Дискретный анализ и исследование операций. Сер. 1. — 2005. — Т. 12, X« 4. — С. 40-50.

33) См., например: Althöfer I. Tight lower bounds on the length of word chains // Inform.

Обозначим через Л* множество всех двоичных наборов (слов) длины п, содержащих ровно к единиц. Положим

lc(k, п) = тах/с(а), к = 0,1,..., п.

¿6 Л*

Доопределим выражение log С*/ log log С* при к = 0 и к = п нулем.

Теорема 1.7. Пусть {(fcm,nm)},m = 1,2,..., — последовательность пар целых чисел, удовлетворяющая условиям: пт —» оо при т —► оо, 0 < кт < пт. Тогда при тп —> оо справедливо асимптотическое равенство

log С*т

lc{kт,Пт) ~ bgnm + --:-

log log С^

При доказательстве верхней оценки этой теоремы в случае, когда log k = o(logn) или log(n — к) = o(logn) оказывается достаточно использовать верхнюю оценку для задачи Кнута. В случае, когда log к ~ log(n—к) ~ logn удается применить к этой задаче метод, разработанный Э. И. Не-чипоруком для доказательства асимптотически точной верхней оценки сложности реализации класса булевых матриц с заданной долей единиц (заданной густоты) вентильными схемами глубины 2. В остальных случат ях для получения асимптотически наилучшей верхней оценки предложен оригинальный метод.

В § 1.5 рассматривается одна задача о сложности вычислений в конечных группах, при исследовании которой важную роль играют оценки, полученные для задачи Беллмана.

Пусть G — конечная группа (групповую операцию будем называть умножением), a Mq — некоторое порождающее множество этой группы. Для каждого элемента g группы G определим его сложность реализации над порождающим множеством Mq, обозначаемую через l(g\ Mq), как минимальное число операций умножения, достаточное для вычисления элемента g с использованием элементов множества Mq (при этом все уже вычисленные элементы могут быть использованы многократно — ив

Process. Lett. — 1990. — V. 34, № 5. — P. 275-276; Berstel J., Brlek S. On the lenght of word chains // Inform. Process. Lett. — 1987. — V. 26, ffi 1. — P. 23-28; Red'kin N. P. Complexity of concatenation schemes for words from some classes // Proceedings of two joint French-Russian seminars on combinatorial and algorithmical properties of discrete structures (April 1998, Moscow — February 1999, Nansy, France). Project No 8/97. — French-Russian A. M. Liapunov Institute, 2001. — P. 107-114.

этом принципиальное отличие от других мер сложности вычислений элементов в группах34)).

Сложность L(G\ Mo) конечной группы G над порождающим множеством Ма определяется тале: L{G\ Mq) = maХд^сКз', Ма).

Для произвольного класса Яп групп порядка п сложность этого класса определяется равенством Ь(Яп) — maxceAri (тахМо L(G\ Ма)) ■

Для сложности абелевых групп при некоторых ограничениях установлена верхняя оценка, асимптотически совпадающая со стандартной «мощ-ностной» нижней оценкой, справедливой для произвольной конечной группы. Кроме того, для класса всех абелевых групп порядка п установлена

Теорема 1.10. При п оо

log log П

Глава 2 посвящена исследованию тех свойств мер сложности I, ^ и которые из каких-либо соображений имеет смысл изучать одновременно для всех трех (или хотя бы для двух) вычислительных моделей.

В § 2.1 доказывается универсальная нижняя оценка, справедливая для всех трех изучаемых мер сложности целочисленных матриц. В ее основе лежат известные соображения об оценке сложности схемы через определитель матрицы, порождаемой вычисляемыми в вершинах схемы функциями. Впервые, по-видимому, рассуждения такого типа для нижних оценок сложности были использованы Ж. Моргенстерном36).

Пусть А — (atj) — произвольная матрица размера р х q, а число к удовлетворяет неравенствам 1 < к < min(p, q). Для наборов индексов (ti,i2, ik) и (ji,j2,...,jk), таких что 1 < ¿1 < г2 < ... < гк < р, 1 < 3\ < 32 < ■ ■ ■ < jk < обозначим через А(ц, i2,..., гк] • • ■, jk) квадратную матрицу порядка к, состоящую из элементов, находящихся на пересечении строк с номерами i2,..., ik и столбцов с номерами jk-

Положим

D(A)= max ( max Idet A(iu i2,..., ik\ ju j2t..., jk)\)■

k: l<*<min(p,g) \(ii,..,tkJl,-Jk) J

34) См., например: Глухов M. М., Зубов А. Ю. О длинах симметрических и знакопеременных групп подстановок в различных системах образующих // Математические вопросы кибернетики, вып. 8. — М.: Наука, 1999. — С. 5-32.

35) Morgenstern J. Note on a lower bound of the linear complexity of the fast Fourier

transform // J. Аззос. Comput. Mach. — 1973. — V. 20. — P. 305-306.

Таким образом, D(A) — это максимум абсолютных величин миноров матрицы А, где максимум берется по всем минорам.

Теорема 2.1. Для любой ненулевой целочисленной матрицы А справедливы неравенства:

1(A) >logD(A), l2(A)> logD(A), lF(A) > logD(A)

(в первом неравенстве подразумевается, что в матрице А нет нулевых строк и все ее элементы неотрицательны).

Большинство доказываемых в данной работе нижних оценок сложности для индивидуальных последовательностей матриц во всех трех вычислительных моделях либо непосредственно следуют из теоремы 2.1, либо существенно ее используют.

В § 2.2 сначала обсуждается многократно открывавшийся и переоткрывавшийся (для разных задач, в разных терминах) так называемый «принцип двойственности»36), который применительно к изучаемым задачам формулируется следующим образом: для любой целочисленной матрицы А размера р х q с неотрицательными элементами без нулевых строк и столбцов справедливо равенство I (АТ) — 1(A) = р — q\ для любой целочисленной матрицы А размера р х q выполняются неравенства -9 < h (Ат) - h(A) < р.

При этом, если во второй вычислительной модели в аддитивной постановке помимо операций х + у и х — у разрешить использование еще и операции —х—у, то для естественным образом определяемой меры сложности ¿2 справедливо утверждение, аналогичное утверждению относительно меры сложности I: для любой целочисленной матрицы А размера р х q без нулевых строк и столбцов справедливо равенство 1'2 (Ат) — l'2(A) = р — q.

В отличие от мер сложности I и 12, мера сложности 1р не обладает свойством двойственности. Действительно, сложность вычисления в третьей модели двух матриц размера, соответственно, 1 X 2 и 2 х 1, получающихся друг из друга транспонированием, может отличаться асимптотически в два раза:

lF ((2k, -2k)) =k + 1, lF ((2*, -2*)T) = 2k.

Прежде, чем переходить к исследованию асимптотического поведения величин 1(A), 12(А) и If(A) в общем случае (для произвольных индивидуальных последовательностей матриц фиксированного или слаборастущего

36) Bernstein D. J. The transposition principle // Available at: http://cr.yp.to/ transposition.html. —2004.

размера), естественно изучить, как это было сделано для меры сложности I Н. Пиппенджером, асимптотическое поведение функций Шеннона для мер сложности ¿2 и 1р.

При К > 2 положим L2(p,q,K) = тах/2(Л), Lp{p,q,K) = max/F(A), где максимум берется по всем целочисленным матрицам А = (a,ij) размера Р х Ч> удовлетворяющим условиям | < К — 1, i = 1,... ,р, j = 1,..., q.

Доказательства двух следующих теорем существенно опираются на результат Н. Пиппенджера, но непосредственно из него не следуют. Более того, несмотря на общее сходство этих двух доказательств, есть и серьезные отличия, делающие попытку объединить их в одно неоправ данной.

Теорема 2.2. При условии pq\og К —> оо справедливо равенство

Я, К) = min(p, q) log К+

, pg\og(2K — 1) (Л , f f\ogloS{pqlogK)Y/2\\ , ^ + log^logtf) {1 + 0 [{ \og{pq\ogK) ) JJ+0(max(p,9));

Стоит отметить тот факт, что при доказательстве верхней оценки теоремы 2.2 предложен способ вычисления системы целочисленных линейных форм, дающий требуемую оценку числа операций и использующий только один раз операцию вычитания.

Теорема 2.3. При условии pq log К —> оо справедливы неравенства

LF(p,q,K) < min(p, q+ l)\ogK+

Lf{p, ff, K) > max (mm{p, q + 1) log ЛГ, ^ogfr^bg K)J + q))'

Таким образом для всех трех вычислительных моделей при слабых ограничениях установлена асимптотика роста соответствующих функций Шеннона, причем во всех трех случаях имеет место эффект Шеннона (при некоторых условиях). Однако можно ожидать (так часто бывает в различных задачах синтеза управляющих систем), что для некоторых достаточно широких классов матриц можно получать существенно лучшие оценки.

В этом направлении естественно исследовать классы матриц, для которых ограничение на величину элемента задается для каждого столбца (каждой строки) индивидуально. В качестве вычислительной модели используется первая модель — в данном случае это не очень принципиально.

Пусть К. = (ki, к2,..., кч) — набор из q натуральных чисел, больших 1. Обозначим через L(K,p) наименьшее число операций умножения, достаточное для вычисления по переменным х\, Х2, ■. ■, xq любой системы одночленов х\11хт21г... Хд1", х[21х%12... хтч2\ ..., Xipli2p2... xrq"\ удовлетворяющей условиям rij < kj — 1, i = 1,..., р, j = 1,..., q.

Без ограничения общности можно считать, что к\ > к2 > ... > кч и выполнено естественное условие р < Л/jc, где Nie = к\к2 ■ ■ - km (т. е. число вычисляемых одночленов не превосходит общего числа одночленов соответствующего вида).

Теорема 2.4. Пусть рlogN^ ->■ оо. Тогда37)

причем если выполняются условия

min (p,q)

то справедливо соотношение

plogNic

L(fC,p)

log(plog JVjc)

Аналогичные оценки справедливы и в случае, когда на величины элементов матрицы ограничения накладываются по строкам, а не по столбцам.

В следующих трех главах изучается асимптотическое поведение величин 1(А), 12{А) и ^(А) для произвольных индивидуальных последовательностей матриц. При этой постановке имеет смысл в первую очередь рассматривать такое соотношение параметров, при котором вклад «мощност-ной» составляющей не является доминирующим. Этому условию удовлетворяет важный случай, когда размеры матриц фиксированы (или слабо растут). При этом отправной точкой, помимо тривиальных верхних оценок, получающихся из оценок соответствующих функций Шеннона, является универсальная для всех трех мер сложности оценка снизу через величину к^.О(Л). Оказывается, что для каждой из трех вычислительных

37) Здесь и далее запись /(х) х д(х) означает одновременное выполнение соотношений }{х) = С{д{х)) и д(х) = 0(/(*))

моделей ситуация при такой постановке сугубо индивидуальна. Для наиболее сильной второй вычислительной модели верхняя оценка асимптотически совпадает с универсальной нижней (при фиксированных или слабо-растущих значениях размеров матриц), для первой модели верхняя оценка асимптотически совпадает с общей нижней только для матриц малой размерности, а для третьей модели уже для матриц размера 2x1 указанная нижняя оценка в некоторых случаях может быть улучшена асимптотически вдвое.

Глава 3 посвящена исследованию задачи о сложности вычисления систем одночленов.

В §3.1 исследуется самый простой случай — вычисление системы из двух одночленов от двух переменных. Основным результатом этого параграфа является

Теорема 3.1. Для произвольной последовательности целочисленных матриц А(п) = (atJ(n)) размера 2x2 с неотрицательными элементами и без нулевых строк, удовлетворяющей при п —> оо условию max0jj.eJ4(„) aij(n) —»■ оо, справедливы оценки

logD(A(n)) < I (А(п)) < ^B(A(n)) + o( [°^22(nL) '

\ log log шах ац(п) J

Из теоремы 3.1 вытекает наличие для исследуемой задачи эффекта Шеннона, который в данном случае заключается в том, что почти все системы из двух одночленов от двух переменных с показателями степеней, не превосходящими п, имеют асимптотически максимальную сложность 21ogn + o(logn). При этом стоит подчеркнуть тот факт, что эффект Шеннона имеет место в задаче, для которой нижние оценки доказываются немощностным методом.

Уже в простейшем случае, когда матрицы имеют размер 2x2, при всей прозрачности основной идеи доказательства верхней оценки, само доказательство технически является довольно громоздким. Для того, чтобы упростить дальнейшие доказательства, выделив в них содержательную часть и проведя техническую работу один раз в общем случае, в §3.1 вводится вспомогательная вычислительная модель, для которой, с одной стороны, доказывать верхние оценки существенно проще, и которая, с другой стороны, допускает при некоторых естественных условиях переход к вычислению в исследуемых моделях без асимптотического увеличения сложности.

В терминах схем из функциональных элементов умножения на примере первой вычислительной модели вводится понятие обобщенной схемы, в которой дополнительно разрешается использование одновходовых элементов, реализующих по подаваемой на вход элемента функции / ее степень /г, где г — рациональное число, удовлетворяющее условию 0 < г < 2 (значение г, вообще говоря, свое для каждого такого элемента). При таком усилении вычислительных возможностей также расширяется и класс вычисляемых матриц: обобщенными схемами можно вычислить любую матрицу с неотрицательными рациональными элементами.

Пусть А — (aij) — матрица размера р х q с неотрицательными рациональными элементами. Через А(Л) обозначается минимально возможная сложность обобщенной схемы из функциональных элементов, реализующей систему функций ... х?', х°21х%22... Хд2\ ..., х^х?2... Хдрч.

Ключевым свойством обобщенных схем является полная определенность со сложностью возведения в степень: при 0 < а < 1 выполняется равенство Х(ха) = 1, а при а > 1 — равенство A(i°) = [loga].

Способ доказательства верхних оценок, основанный на оценках сложности обобщенных схем заключается в следующем. Сначала для целочисленной матрицы А строится обобщенная схема нужной сложности (например, сложности logZ)(.A) + 0(1)), причем эта обобщенная схема помимо ограничения на сложность должна обладать еще одним важным свойством — допускать разбиение на ограниченное (речь идет о вычислении последовательности матриц) или слаборастущее число подсхем, каждая из которых либо состоит из одного двухвходового функционального элемента, либо имеет один вход, один выход, и, соответственно, вычисляет некоторую степень подаваемой на вход подсхемы функции (подсхемы этих двух типов называются простейшими). После этого построенная обобщенная схема перестраивается без асимптотического увеличения сложности в обычную схему, вычисляющую ту же матрицу А. Возможность такого перестроения устанавливает

Теорема 3.2. Пусть элементы последовательности целочисленных матриц А(п) - (а^(п)) размера р(п) х q(n) с неотрицательными элементами и без нулевых строк, п = 1,2,..., удовлетворяющей при п —» оо условию max а^(п) —¥ ос, вычисляются обобщенными схемами S(n), со-

<ч,еА(п)

стоящими из к(п) простейших подсхем, причем выполняются неравен-

ства

1/2

k{n) < (log log log max atj(n) \ dij£A(n) ,

1 ( \1/2 я(п) < - log log log max Oy(n) ) б \ aij£A{n) J

Тогда справедливо соотношение

(log max a¡j(n) ■os.,;;"!! „(,)

atj£A(n) ,

Аналогичные утверждения справедливы также для второй и третьей вычислительной модели.

Далее описанным выше способом доказывается

Теорема 3.3. Для произвольных последовательностей целочисленных матриц А(п) = (а^-(п)) и В{п) = (b¿3(n)) размеров, соответственно, р(п) х 2 и 2 х <у(п) с неотрицательными элементами и без нулевых строк, удовлетворяющих при п —* оо условиям

р(п) = о ^logloglog^max ^ ^ ,

q{n) = о ^ ^log log log ь max ^ b¡j(n)^ j , справедливы оценки

* D^ £1W-» - * в ■+'' (ю^ЙЫ ■

ъщвы) < ,(В(п}) < iogD(B(n))+. .

В § 3.3 также путем сведения к реализации обобщенными схемами устанавливается асимптотическая формула для сложности вычисления системы из трех одночленов от трех переменных.

Теорема 3.4. Для произвольной последовательности целочисленных матриц А(п) = (Оу(п)) размера 3 х 3 с неотрицательными элементами и без нулевых строк, удовлетворяющей при п —»• оо условию таХ(,^6д(п) aij(n) —> оо, справедливы неравенства

logD(A(n)) <l(xailyai2zai3,xa21ya22za23,xa31ya32za33) <

< log D(A(n)) + о (log D{A{n))).

При доказательстве этой теоремы приходится исследовать большое число случаев, часть из которых довольно проста, однако для некоторых случаев требуется серьезный анализ.

Частичное разъяснение природы трудностей, возникающих при доказательстве верхней оценки теоремы 3.4 дают результаты из § 3.4. Логично вытекающее из теорем 3.1, 3.3 и 3.4 предположение о том, что, возможно, при всех фиксированных значениях р и q для матриц размера р х q величина 1(A) асимптотически растет как log D(A) (косвенным доводом в пользу этого предположения является справедливость в аналогичных условиях формулы h(A) ~ logD(A) — об этом говорится подробнее в следующей главе), оказывается неверным уже для квадратных матриц порядка 4.

Обозначим через A(t, п) квадратную матрицу порядка 2t, t > 2, определяемую таким образом. Первой строкой матрицы A(t, п) является набор длины 2t, первая половина разрядов которого равна п, а вторая половина — 0. Остальные 2t — 1 строк матрицы A(t, п) получаются из первой строки последовательным циклическим сдвигом на один разряд вправо.

Теорема 3.5. При условии t = o(logn) справедливо асимптотическое равенство

l(A(t,n)) ~ 2Hogn.

Следствием этой теоремы является такое утверждение — при условии t < log п/ log log п выполняется соотношение

l(A(t,n))~^\ogD(A(t,n)).

Таким образом, помимо прочего, приведен пример последовательности матриц размера 21 х 21, для которой устанавливаемую теоремой 2.1 нижнюю оценку в рамках первой вычислительной модели можно усилить асимптотически в 2t/(t+ 1) раз.

Глава 4 посвящена исследованию задачи о сложности вычисления целочисленных линейных форм. Для этой задачи получен в некотором смысле (а именно, с точки зрения асимптотики) окончательный результат.

Теорема 4.1. Пусть последовательность целочисленных матриц А(п) = (a¿j(n)) размера р(п) х q(n) при п —¥ оо удовлетворяет условию

р{п) + g(n) _^ о (log log D{A{n)))1^2

Тогда

\ogD(A(n)) < l2 (A(n)) < logL^n)) + o(logD(A(n))).

В формулировке этой теоремы можно указать более слабые ограничения (при этом более сложного вида), при которых справедлива верхняя оценка вида log + о( log D{A)^. Однако, наиболее принципиальным

представляется содержащееся в теореме 4.1 утверждение о том, что для любых фиксированных (и даже слаборастухцих) значениях размеров задающей систему функций матрицы верхняя оценка сложности вычисления этой системы асимптотически совпадает с нижней.

Из теорем 3.4 и 4.1 также следует, что при переходе от первой вычислительной модели ко второй, т. е. при добавлении возможности кроме основной операции использовать дополнительную (вычитание или деление в зависимости от интерпретации) сложность вычисления может значительно уменьшаться.

Глава 5 посвящена исследованию задачи о сложности вычисления систем элементов свободных абелевых групп. Мера сложности 1р значительно отличается по своим свойствам от мер сложности I и В частности, как уже отмечалось, применительно к ней не работают (или работают не в достаточной мере) соображения двойственности:

lF ((2*, —2*)) = к + 1, lF ((2fc, -2fc)T) = 2к.

Последнее равенство можно переписать так:

Zí-((2fe,-2fc)T)=21ogD(((2fc,-2fc)T),

что сразу дает пример нижней оценки, вдвое большей, чем дается теоремой 2.1 — для меры сложности ¿2 при фиксированных размерах матриц

в силу теоремы 4.1 такого эффекта (с точки зрения асимптотики) быть не может, а для меры сложности I — такого эффекта не может быть для матриц малого размера.

В § 5.1 исследуются самые простые случаи — когда матрицы имеют размеры 1 х g, р х 1 и 2 х 5. И если в первом случае рост сложности вычисления в третьей модели устанавливается как простое следствие предыдущих результатов, то для последних двух типов матриц при изучении асимптотики роста обнаруживается новый эффект.

Для произвольной матрицы А размера рхд определим величину Т(А) равенством

т(л) = . max {тах{аъ , a2j,..., apj} 0} |min{oij, a2j,..., apj, 0}|} .

1SJS?

Таким образом, T(A) — это максимум абсолютных величин попарных произведений элементов матрицы А, где максимум берется по всем парам элементов, удовлетворяющим двум условиям — эти элементы должны находиться в одном столбце и иметь разные знаки (если таких пар нет, то Т{А) = 0).

С использованием теоремы 2.1 в работе устанавливается справедливость для любой целочисленной матрицы А неравенства If{A) > logmax{T(>l), 1}. Величина logT(A), вообще говоря, может превосходить величину logZ?(j4), но не более, чем в 2 раза.

Теорема 5.3. Для произвольной последовательности целочисленных матриц А(п) = (а*^(п)) размера 2 х q(n), удовлетворяющей условию

яЧ v 0

log log max (n) |

при n -4 00, справедливо асимптотическое равенство lF(A(n)) ~ ]ogmax{£>(A(n)),T(A(7i))}.

Еще более нетривиальная ситуация возникает в изучаемом в § 5.2 случае матриц размера 3x2, для которого также установлена асимптотика роста величины

Пусть матрица А — (а¿¿) имеет размеры 3x2. Под записью a3t при s > 3 или t > 2 будем понимать элемент atJ-, где г и j определяются из условий 1 < г < 3, г = s (mod 3); 1 < j < 2, j = t (mod 2).

Элемент atJ- матрицы А размера 3x2 называется особым, если выполняются следующие условия:

a-ij ф °i aijdi+ij < 0, aijai+2j < 0, |ai+lj-| + |aI+2,j| ф 0.

Через A(s,t) обозначим матрицу размера 2 х 2, в которой первой строкой является строка матрицы А, содержащая элемент а31, а второй — строка матрицы А, содержащая элемент ац.

Пусть dij — особый элемент матрицы А размера 3x2. Определим величину r(üij) следующим обазом:

1) если выполняются неравенства det A(i + 1, i + 2) det A(i + 2, г) > 0 и det A(i + 1, г + 2) det A(i, i + 1) > 0, то полагаем

r(aij) = |an det A(i + 1, i + 2)|;

2) если выполняется неравенство det A{i + 1, i + 2) det A(i + 2, г) < 0, то полагаем

T(aij) = det A(t + 1, г + 2)|-D{A{i + 2,i))-'

3) если выполняется неравенство det.4(i +1, г + 2) det A(i, i + 1) < 0, то полагаем

гМ = |atJ det A{i + 1, г + l^L K+i,l}

Для элементов Oij, не являющихся особыми в целочисленной матрице А размера 3x2, положим г(а^) — 0. Далее, для матрицы А определим величину R{A) равенством

R{A) = тахт-(ац).

а ц€А

Теорема 5.4. Для произвольной последовательности целочисленных матриц А(п) = {а^(п)) размера 3x2, удовлетворяющей при п —> оо условию

шах |о0(п)| -> 0,

а^еЛ(п)

справедливо асимптотическое равенство

lF(A(n)) ~ logmax{D(A(n)),T(A(n)), R(A(n))}.

Величина R(A) в последнем соотношении может быть определяющей — например, для матрицы

/-га 0\ А = 71 О \0 га/

выполняются равенства D(A) = Т(А) - га2, R{A) = га3.

В § 5.3 для матриц A(t, га), введенных в § 3.4, изучается сложность вычисления в третьей модели, причем асимптотика роста отличается от той, что была установлена для этой последовательности матриц в теореме 3.4 при вычислении в первой модели.

Теорема 5.5. При условии t = о справедливы асимптотиче-

ские равенства

lF{A(t,n)) ~ {t + 1) log га ~ logD(,4).

Таким образом, переход от первой вычислительной модели к третьей, т. е. добавление не очень важной на первый взгляд возможности использования помимо переменных обратных к ним величин, может существенно менять ситуацию при вычислении системы одночленов.

Теорема 5.6. При условии t = o(logn) справедливо асимптотическое равенство

l(A(t,n)) 2t lF(A(t,n)) ~ t + 1"

Рассматриваемые в работе матрицы A(t, га) вырождены — при размере 21 х 2t они имеют ранг t + 1. Однако эти матрицы можно немного «подправить», увеличив на 1 диагональные элементы at+2,t+2, o-t+xt+з, ■ ■ ■, a2t,2t-Полученные матрицы A!(t,n), с одной стороны, невырождены и удовлетворяют равенствам D(A'(t,n)) = detyl'^.n) = rai+1 = D(A(t, га)), а с другой стороны, для них все оценки сложности сохраняются практически без изменений.

Появление данной работы было бы невозможно без Олега Борисовича Лупанова. Автор рассматривает эту работу как скромную дань памяти своего учителя.

СПИСОК ОСНОВНЫХ РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ, ОПУБЛИКОВАННЫХ В ВЕДУЩИХ РЕЦЕНЗИРУЕМЫХ НАУЧНЫХ ЖУРНАЛАХ И ИЗДАНИЯХ (В СООТВЕТСТВИИ С ПЕРЕЧНЕМ ВАК)

1. Кочергин В. В. Об аддитивных вычислениях систем целочисленных линейных форм // Вестник Московского университета. Сер. 1. Математика. Механика. — 1993. — № 6. — С. 97-101.

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

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

4. Кочергин В. В. О сложности вычислений в конечных абелевых, ниль-потентных и разрешимых группах // Дискретная математика. — Т. 5, вып. 1. — 1993. — С. 91-111.

5. Кочергин В. В. О сложности вычислений в конечных нильпотентных группах // Дискретный анализ и исследование операций. — 1996. — Т. 3, № 1. — С. 43-51.

6. Кочергин В. В. О сложности вычисления систем одночленов с ограг ничениями на степени переменных // Дискретная математика. — Т. 10, вып. 3. — 1998. — С. 27-34.

7. Кочергин В. В. О мультипликативной сложности двоичных слов с заданным числом единиц // Математические вопросы кибернетики, вып. 8. — М.: Наука, 1999. — С. 63-76.

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

9. Кочергин В. В. Об асимптотике сложности аддитивных вычислений систем целочисленных линейных форм // Дискретный анализ и исследование операций. Серия 1. — 2006. — Т. 13, № 2. — С. 38-58.

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

11. Кочергин В. В. О максимальной сложности совместного вычисления систем элементов свободной абелевой группы // Вестник Московского университета. Сер. 1. Математика. Механика. — 2007, № 3. — С. 14-19.

СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ, ОПУБЛИКОВАННЫХ В ИЗДАНИЯХ, НЕ ВХОДЯЩИХ В ПЕРЕЧЕНЬ ВАК

12. Кочергин В. В. Об одном классе аддитивных цепочек // Теоретические и прикладные аспекты математических исследований (сборник трудов конференции молодых ученых механико-математического ф-та МГУ). — Москва: Изд-во Московского университета, 1994. — С. 9-13.

13. Кочергин В. В. О сложности некоторых мультипликативных вычислений // Материалы^II межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Минск, 13—16/XI 1995). — Москва: Изд-во механико-математического факультета МГУ, 1996. — С. 16-18.

14. Kochergin V. V. Some generalizations of addition chains problem // Proceedings of two joint French-Russian seminars on combinatorial and algo-rithmical properties of discrete structures (April 1998, Moscow — February 1999, Nansy, France). Project No 8/97. — French-Russian A. M. Liapunov Institute, 2001. — P. 33-41.

15. Кочергин В. В. О сложности получения двоичных слов с заданным числом единиц схемами конкатенации // Труды III Международной конференции "Дискретные модели в теории управляющих систем" (22-27 июня 1998 г.). — Москва, Диалог-МГУ, 1998. — С. 58-62.

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

17. Кочергин В. В. О сложности вычисления системы одночленов специального вида // Материалы X Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Минск, 29 ноября - 3 декабря 1999 г.). - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2000. — С. 12-14.

18. Кочергин В. В. О некоторых обобщениях задачи об аддитивных цепочках // Дискретная математика и ее приложения. Сборник лекций. — М.: Изд-во Центра прикладных исследований при механико-математическом факультете МГУ, 2001. — С. 59-83.

19. Кочергин В. В. О сложности вычисления систем одночленов от двух переменных // Труды VII Международной конференции *Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта 2006 г.). — М.: МАКС Пресс, 2006. — С. 185-190.

20. Кочергин В. В. О сложности совместного вычисления двух эле-

ментов свободной абелевой группы // Материалы XVI Международной школы-семинар а «Синтез и сложность управляющих систем* (Санкт-Петербург, 26-30 июня 2006 г.). — М.: Изд-во механико-математического факультета МГУ, 2006. — С. 54-59.

21. Кочергин В. В. Об аддитивной сложности целочисленных матриц размера 3x2// Материалы IX Международного семинара *Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, 18-23 июня 2007 г.). — М.: Изд-во механико-математического факультета МГУ, 2007. — С. 99-102.

22. Кочергин В. В. О сложности вычисления систем одночленов и систем целочисленных линейных форм // Дискретная математика и ее приложения. Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. Выпуск III. — М.: Изд-во механико-математического факультета МГУ, 2007. — С. 3-63.

23. Кочергин В. В. О сложности совместного вычисления трех элементов свободной абелевой группы с двумя образующими // Дискретный анализ и исследование операций. Серия 1. — 2008. — Т. 15, № 2. — С. 23-64.

24. Кочергин В. В. Замечание о сложности вычисления систем одночленов // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Казань, 2-7 июня 2008 г.). — Казань: Отечество, 2008. — С. 62.

Издательство ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова

Подписано в печать 02.09.08 Формат 60x90 1/16. Усл. печ. л. 2,0 Тираж 0О экз. Заказ 40

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

2007518103

n

2007518103

Введение

1. Задачи Беллмана и Кнута

§ 1.1. Определения. Постановка задачи в общем виде. Задачи Беллмана и Кнута.

§ 1.2. Верхние оценки

§ 1.3. Нижние оценки

§ 1.4. Применение задачи Кнута к оценкам сложности схем конкатенации

§ 1.5. Сложность вычислений в конечных группах

2. Общие свойства мер сложности I, ¿2? ^

§ 2.1. Универсальная нижняя оценка.

§2.2. Функции Шеннона.

3. Вычисление систем одночленов

§3.1. Случай матриц размера 2x2.

§ 3.2. Вспомогательная модель — обобщенные схемы.

§ 3.3. Случай матриц размера 3x3.

§ 3.4. Сложность одной системы из 2t одночленов от 21 переменных

4. Вычисление систем целочисленных линейных форм

5. Вычисление систем элементов свободной абелевой груп

§ 5.1. Случай матриц размера 1 X д, р X 1 и 2 X д

§ 5.2. Случай матриц размера 3x

§ 5.3. Сравнение двух мер сложности для одной последовательности систем из 2£ одночленов от 2t переменных

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Данная работа относится к одной из центральных областей дискретной математики и математической кибернетики — теории синтеза и сложности управляющих систем, получающей постановки задач и находящей многообразные применения в информатике и вычислительной технике.

Проблему синтеза управляющих систем кратко можно сформулировать следующим образом. Задан запас элементов (базис), реализующих некоторые функции. Заданы правила построения из элементов более сложных объектов — схем, а также задан способ нахождения по схеме реализуемой (вычисляемой) ею функции; схема определяет строение, а функция — поведение управляющей системы или модели вычислений. Задача состоит в построении для каждой рассматриваемой функции схемы, которая реализует эту функцию, причем обычно важно не просто построить схему, но и добиться, чтобы она была в каком-то определенном смысле наилучшей. Качество схемы обычно выражается с помощью какой-либо из мер сложности, среди которых рассматриваются, например [58, 17, 50, 123, 57, 4, 14], число элементов, стоимость, занимаемые объем или площадь, глубина, задержка, мощность и др.

Если базис является конечным, то существует тривиальный переборный алгоритм решения этой задачи. Однако реально воспользоваться им чаще всего невозможно, так как с ростом числа элементов в схемах количество схем растет очень быстро и применение тривиального метода становится практически неосуществимым. На самом деле большая трудоемкость решения задачи синтеза в общем виде присуща всем алгоритмам, предназначенным для ее решения, — к этому выводу одним из первых пришел С. В. Яблонский [80]. С тех пор эта точка зрения стала общепринятой, получив много косвенных подтверждений своей справедливости. В силу этого обычно рассматривают некоторые ослабления рассматриваемой задачи. Одно из таких ослаблений заключается в приближенном решении задачи, т. е. в построении не обязательно минимальных, а «достаточно экономных» схем. Но и эта задача при поиске «достаточно точного» решения, вообще говоря, остается очень трудной. Поэтому часто рассматривают задачу построения асимптотически оптимальных схем. Постановка этой задачи, скажем, для классического случая вычисления булевых функций такова. Каждой схеме 5 ставится в соответствие неотрицательное число Ь(5) — сложность схемы 5, например, число элементов схемы. Считается, что схема тем лучше, чем меньше величина ¿(5). Через £(/) обозначается сложность схемы из заданного класса, которая реализует / и имеет минимальную сложность. Вводится функция Ь(п) = тахЬ(/), где максимум берется по всем рассматриваемым функциям от п переменных. Требуется найти метод синтеза схем, позволяющий для любой рассматриваемой функции /отп переменных стоить схему, которая реализует / и имеет сложность, не превосходящую или мало превосходящую величину Ь(п). Такой подход был предложен К. Шенноном [137] в 1949 г. при исследовании контактных схем и может быть перенесен на другие классы управляющих систем. Функцию Ь(п) принято называть функцией Шеннона.

Фундаментальные основы асимптотической теории синтеза и сложности управляющих систем были заложены О. Б. Лупановым. Им были предложены асимптотически оптимальные методы синтеза и получены асимптотически точные оценки сложности для важнейших классов управляющих систем — вентильных схем глубины 2, контактно-вентильных схем, схем из функциональных элементов, контактных схем, схем из функциональных элементов без ветвления выходов (формул) и с ограниченным ветвлением (формул с частичной памятью), формул ограниченной глубины, параллельно-последовательных контактных схем, релейно-контактных схем и др. — см., например, [58, 68]. При изучении этих модельных классов управляющих систем О. Б. Лупановым были выявлены новые эффекты и закономерности, в числе которых было явление, названное эффектом Шеннона: при реализации в большинстве исследованных им классов управляющих систем почти все функции имеют почти одинаковую сложность, асимптотически равную сложности наиболее сложных функций. О. Б. Лупановым был сформулирован и обоснован важнейший общий принцип теории синтеза и сложности управляющих систем — принцип локального кодирования [56], являющийся основным инструментом оптимального синтеза для функций из специальных классов.

К асимптотической теории синтеза и сложности управляющих систем относятся и вопросы, исследуемые в данной работе. При этом часть изучаемых вопросов следует отнести к области построения универсальных методов синтеза (расчитанных на реализацию произвольных функций), а другую — к области синтеза схем для конкретных (индивидуальных) функций (последовательностей функций).

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

В работе изучаются различные обобщения хорошо известной задачи о сложности возведения в степень, т. е. задачи о нахождении величины l(xn) — минимального числа операций умножения, достаточного для вычисления по переменной х величины хп. Эту задачу (а также ее обобщения) обычно рассматривают в аддитивной постановке — это известная задача об аддитивных цепочках, которая формулируется следующим образом (см., например, [15]). Аддитивной цепочкой для натурального числа n называется всякая последовательность целых чисел а0 = 1? аЪ • • • 1 ат — П, удовлетворяющая следующему свойству: для каждого k, 1 < к < m, найдется два целых числа (не обязательно различных) г и j, 0 < г, j < к — 1, таких, что dk = ai + aj. Минимальная длина m аддитивной цепочки для п называется аддитивной сложностью числа п и обозначается 1{п). Очевидно, что величины 1{п) и 1(хп).

Считается [15], что задачу определения величины 1{п) поставил в 1894 r. X. Деллак, хотя, по-видимому, еще в древней Индии был известен «бинарный» метод возведения в степень (см., например, [98]). В 1937 г. А. Шольц [135] для этой задачи ввел понятие аддитивной цепочки.

В 1939 А. Брауэром [93] для величины 1{п) при n —> оо была установлена асимптотическая формула1) l(n) ~ logn, причем им была получена верхняя оценка < logn+ri2^- + О C°g"logloglogn\ log logn \ (loglogn)^ J

В 1960 г. П. Эрдёш [105] показал, что для почти всех n справедливо асимптотическое равенство

I n = log п + —f-+ о —f- , log log n \ log log n J

Здесь и далее logx означает log2 x, а запись f(n) ~ g(n) означает, что при n —> оо f(n) 1 отношение стремится к 1. при этом стоит отметить разную природу слагаемых в правой части этого равенства — слагаемое logn связано с величиной числа п и должно присутствовать для любого значения п, а «мощностное» (отношение логарифма количества чисел, не превосходящих п, к повторному логарифму) слагаемое зависит от «строения» числа п и присутствует для «почти всех» п.

После этого исследовались (как правило, на языке аддитивных цепочек) различные вопросы, связанные с задачей о наискорейшем возведении в степень — см., например, обзоры [141, 91, 107, 15, 86].

В частности, была опровергнута правдоподобная гипотеза о том, что удвоение (степени) очень эффективный шаг, т. е. что l(2n) = l(n) +1. Однако с помощью машинных вычислений установлено, что ¿(191) = ¿(382).

Также стоит выделить исследования (см., например, обзоры [110, 142]), связанные с гипотезой Шольца — Брауэра, утверждающей, что 1(2т — 1) < т — 1 + 1{т). В связи с этим представляется интересным результат А. Шенхаге [136]: l(n) > logn + logs(n) — 2,13, где s(n) — число единиц в двоичной записи числа п.

Теперь перейдем к обобщениям задачи об аддитивной сложности натурального числа (или задачи о наискорейшем возведении в степень). Эти обобщения, по-существу, являются основными объектами исследования данной работы.

Пусть А = (a¿j) — целочисленная матрица размера р х q с неотрицательными коэффициентами без нулевых строк.

Аддитивной цепочкой для матрицы А называется [113] последовательность д-мерных векторов (наборов) вида vi = (l,0,.,0),v2 = (0,l,.,0),.,v9= (0,0,.,1), начинающаяся с q единичных векторов и удовлетворяющая условиям:

1) для каждого &,д+1<&<д + г, найдется два натуральных числа (не обязательно различных) ги^', 1 < { < к — 1, 1 < 3 < к — таких, что ^к — V« + V,- (сложение векторов покомпонентное);

2) {(ап

С {УЬУ2,.,Уд+г}.

Число г называется длиной цепочки. Минимальная длина аддитивной цепочки для матрицы А называется аддитивной сложностью (вычисления, порождения, реализации) матрицы А и обозначается через 1(А).

Задача об аддитивной сложности матриц по-существу совпадает с известной (см., например, [131, 147, 61, 86]) задачей о сложности вычисления систем одночленов (систем коммутативных мономов) — величина 1(А) численно равна минимально возможному числу операций умножения, достаточному для (схемного) вычисления по переменным х\, Ж2, • •., хд задаваемой матрицей А системы одночленов сцг агч г а21 а22 а2д £ „ар1„ар2 арч

Л — л2 • • • -Ьд ) J2 — Л2 ' ' ' ^Lq ' • • • 1 Зр — Л2 • * ■ > при этом допускается многократное использование промежуточных результатов) .

Пусть теперь А = (а^) — произвольная (не обязательно с неотрицательными элементами и без нулевых строк) целочисленная матрица. Определим еще две меры сложности порождения таких матриц.

Через ^(А) обозначим минимальную длину таких аддитивных цепочек для матрицы А, в которых помимо операции сложения (у& = у^ + у?) разрешена и операция вычитания (ук = ^ — у^). Величина Ь{А) численно равна минимально возможному числу операций умножения и деления, достаточному для (схемного) вычисления по переменным Х\,Х2, ■ ■ • ,хд задаваемой матрицей А системы функций = х^х^2. Хдгд, г = 1, 2,. ,р, а также минимально возможному числу операций сложения и вычитания, достаточному для (схемного) вычисления по переменным #2, • • •, хя задаваемой матрицей А системы целочисленных линейных форм д^ = ацХ\ + Щ2Х2 +. + сцдхя, г = 1,2,. ,р. В таком виде задача о нахождении величины Ь(А) поставлена, к примеру, в [74].

Эта мера сложности тесно связана с быстрыми вычислениями на эллиптических кривых [103, 107, 120, 125] и имеет два мало отличающихся друг от друга варианта — не допускающий операции вида у^ = —V« — у.,-, как в [74, 89, 108, 148] и допускающий такие операции — как

Через 1р(А) обозначим минимальную длину таких аддитивных цепочек для матрицы А, в которых используется только операции сложения = у« + у^), но которые начинаются не с д начальных единичных векторов, а с 2д векторов — помимо векторов V!, у2, ., у9 разрешается использовать противоположные к ним векторы —VI, — • • •, — Величина /р(А) численно равна минимально возможному числу операций умножения, достаточному для (схемного) вычисления по образуюг = 1,2,. ,р, элементов этой группы. Впервые, по-видимому, такая мера сложности исследовалась в [139] (причем не только для коммутативного случая).

Величины 1(А), ¡2 {А) и 1р(А) можно интерпретировать как минимально возможную сложность (число элементов) схемы из функциональных элементов [55, 72, 76], на входы которой подаются переменные ж2,. •, хд (а также обратные к ним величины ж^1, х^1, ■ ■ •, хесли речь идет о мере сложности 1р), на выходах схемы вычисляются функции /1, /2, • • •, /р, задаваемые матрицей А, а сама схема состоит из двухвходовых элементов, реализующих произведение (произведение или частное, если речь идет о мере сложности ¿2) функций, подаваемых на входы элемента.

В 1963 г. Р. Беллман [84], а затем в 1964 г. Е. Страус [140] сформулировали задачу о сложности вычисления одночлена от д переменных (в наших обозначениях — случай р = 1, мера сложности — /), т. е. нахождев [118, 120, 125, 128]. щим XI, Х2,. ■ ■, хд [ группы и к ним элементам х ., х~г задаваемой матрицей А системы = х^х^2 ■. Хд1д,

-гд ния величины /(ж"1^2 • • • ж<79)

В 1969 г. Д. Кнут [15, разд. 4.6.3., упр. 32] поставил задачу о сложности вычисленияр степеней одной переменной (в наших обозначениях — случай д = 1, мера сложности — I), т. е. нахождения величины 1(ха1,ха2,., хар). Е. Страус [140] показал, что для любого фиксированного д при а,{ —> оо справедлива асимптотическая формула х^х^2. х^) ~ к^тах^).

А. Яо [151] установил аналогичную формулу для любого фиксированного р при

1(ха1 ,ха2,.: хар) ~ log(max щ).

Далее отметим результат Д. Добкина и Р. Липтона [100], которые установили асимптотически точное значение сложности вычисления набора степеней для одного частного случая, упоминавшегося Д. Кнутом при постановке общей задачи, — когда набор показателей степеней является последовательностью квадратов идущих подряд, начиная с единицы, натуральных чисел. Они, с использованием результатов Т. Соузарда [138], показали, что при р —оо причем

1(х12,х*,.,х?) >р + р2/3-£ для любого положительного е при всех достаточно больших р.

В 1981 г. независимо А. Ф. Сидоренко [74], Дж. Оливосом [129], а также Д. Кнутом и К. Пападимитриу [113] было доказано, что в действительности задачи о сложности вычисления одночлена от т переменных и набора т степеней эквивалентны (и, следовательно, достаточно исследовать одну из них). На самом деле справедливо более сильное утверждение [74, 113, 8, 147] о двойственности относительно меры сложности I: сложность системы одночленов {/1? /2,., /р} от q переменных, заданной матрицей А = (а^) размера р х q и сложность двойственной системы одночленов {/i, /2,., fq} от р переменных, заданной транспонированной матрицей Ат = (а^) размера q X р, для любой матрицы А без нулевых строк и столбцов связаны соотношением

Ч /Ч /-ч

Н/ь /2, • • •, /р) +Р = К/ь /2, • • •, Л) + q, т. е. для любой целочисленной матрицы А с неотрицательными элементами размера р х q без нулевых строк и столбцов выполняется равенство l(A)+p = l(AT)+q.

В работе [74] показано, что похожее соотношение для двух матриц, получающихся друг из друга путем транспонирования, справедливо и для меры сложности ¿2

Также в 1981 г. в работе [101] установлено, что задача распознавания по набору натуральных чисел (щ, щ,., пр, I) существования аддитивной цепочки, имеющей длину I и содержащей числа щ, П2,. •, пр, является iVP-полной. В связи с этим дополнительный вес приобретает асимптотическая постановка исходной задачи. Требуется найти метод построения для матрицы А аддитивной цепочки (соответствующего типа), длина которой в том или ином смысле близка к значению 1(A), h(A) или If (А) соответственно. Например, такой метод, что отношение длины построенной цепочки для матрицы А = (а^) к значению соответствующей меры сложности матрицы стремилось к 1 при ^ —»■ оо для всех или «почти всех» матриц.

Существенным продвижением в этом направлении стала работа Н. Пиппенджера [131]. В ней исследовано асимптотическое поведение функции Шеннона, характеризующей сложность «самой сложной» матрицы среди матриц заданного размера с элементами, не превосходящими заданного значения К — 1, и определяемой при К > 2 равенством

L(p,q:K) = max 1(A), где максимум берется по всем целочисленным матрицам А = (dij) с неотрицательными элементами без нулевых строк размера pXq, удовлетворяющим условиям ац < К — 1, г = 1,. ,р, j = 1,., q. С использованием своего технически весьма громоздкого и существенно опирающегося на результаты О. Б. Лупанова [53] и Э. И. Нечипорука [67] способа [132] построения асимптотически оптимальных обобщенных вентильных схем, реализующих целочисленные матрицы с неотрицательными элементами, Пиппенджер показал, что при условии pq log К —> оо имеет место асимптотическое равенство

L(p, q, К) = min(p, q) log K+

Однако для конкретных (индивидуальных) матриц (последовательностей матриц) никаких нетривиальных асимптотически точных оценок сложности, кроме случая р = 1 при фиксированном q или q = 1 при фиксированном р, ни для одной из определенных здесь мер сложности известно, по-видимому, не было.

Целью диссертационной работы является исследование асимптотических закономерностей поведения величин 1(А), 12 (А) и 1р(А) при ограниченных или слаборастущих значениях размеров целочисленных матриц А, построение асимптотически оптимальных методов вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободной абелевой группы, поиск и изучение новых эффектов в этой области, а также исследование зависимостей поведения описанных мер сложности целочисленных матриц от параметров самих матриц.

При решении поставленных задач использовались методы дискретной математики и математической кибернетики.

Все основные результаты диссертации являются новыми. Основные положения, выносимые на защиту, следующие: log (pq log К) pq log К

Для задачи о сложности вычисления одночлена от нескольких переменных (задача Беллмана) и для задачи о сложности вычисления набора степеней одной переменной (задача Кнута) при слабых ограничениях в области изменения параметров получены асимптотически точные решения.

С использованием полученных оценок сложности вычисления наборов степеней установлена асимптотика роста сложности вычисления двоичных слов с заданным числом (или долей) единиц схемами конкатенации.

Установлена общая нижняя оценка сложности вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободных абелевых групп.

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

Для любых фиксированных (или слаборастущих) значениях р и q установлена асимптотика роста сложности вычисления системы из р целочисленных линейных форм от q переменных.

Доказаны асимптотически точные верхние оценки сложности вычисления: системы из двух элементов свободной абелевой группы, системы из трех элементов абелевой группы с двумя образующими.

Выявлены новые эффекты в задачах о сложности вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободных абелевых групп.

• Установлены принципиальные различия в асимптотическом поведении трех исследуемых мер сложности.

Работа носит теоретический характер. Ее результаты могут быть использованы при исследовании различных вопросов теории сложности. Некоторые разделы диссертации могут быть использованы в специальных курсах для студентов и аспирантов, обучающихся по специальности математика.

Научные результаты и положения диссертационной работы докладывались и обсуждались на следующих научных конференциях, семинарах и школах-семинарах: серии всесоюзных (затем международных) конференций «Проблемы теоретической кибернетики» — Волгоград (1990), Саратов (1993), Ульяновск (1996), Нижний Новгород (1999), Казань (2002), Пенза (2005), Казань (2008, пленарный доклад); серии международных семинаров «Дискретная математика и ее приложения» — Москва, МГУ (1993, 1995, 1998, 2004, 2007); серии всесоюзных (впоследствии международных) школ-семинаров «Синтез и сложность управляющих систем» — Ташкент (1990), Нижний Новгород (1992, 1994, 1996, 1998, 2000), Минск (1993,1995,1999), Санкт-Петербург (2006, пленарный доклад); серии международных конференций «Дискретные модели в теории управляющих систем» (1997, 1998, 2000, 2006); а также на совместном французско-российском семинаре «Combinatorial and algorithmical properties of discrete structures» (1999), на международной школе-семинаре «Сложность булевых функций» (Казань, 1999). Большинство из этих докладов нашли отражение в трудах, материалах, тезисах или аннотациях докладов соответствующих конференций и семинаров. Основные результаты диссертации многократно докладывались в МГУ им. М. В. Ломоносова на научно-исследовательских семинарах «Математические вопросы кибернетики» (руководители — С. В. Яблонский; О. Б. Лупанов; О. М. Касим-Заде), «Синтез управляющих систем» (руководители — О. Б. Лупанов; О. М. Касим-Заде), «Синтез управляющих систем и смежные вопросы» (руководители — О. Б. Лупанов и В. М. Храпченко) и других, а также на Ломоносовских чтениях в МГУ.

По теме диссертационной работы автором опубликована 31 печатная работа [20-49, 116], основными из которых являются публикации [20, 2226, 28, 30, 32, 35-38, 40-49, 116].

Диссертационная работа состоит из введения, пяти глав и списка использованной литературы из 151 наименования. Полный объем работы составляет 344 страницы. Работа содержит 21 рисунок. Нумерация теорем, лемм, утверждений, следствий, замечаний и формул — двойная, состоящая из номера главы и собственно номера внутри данной главы. Например, теорема 3.4 — это четвертая теорема в главе 3.

1. Андреев А. Е. О сложности градиентных вентильных схем // Дискретная матемематика. — 1995. — Т. 7, К5 1. — С. 66-76.

2. Андреев А. Е. О сложности реализации вентильными схемами не-доопределенных матриц // Математические заметки. — 1987. — Т. 41, № 1.

3. Белага Э. Г. Аддитивная сложность натурального числа // Доклады АН СССР. — 1976. — Т. 226, № 1. — С. 15-18.

4. Вайнцвайг М. Н. О мощности схем из функциональных элементов // Доклады АН СССР. — 1961. — Т. 139, № 2. — С. 320-323.

5. Вальский Р. Э. О наименьшем числе умножений для возведения в данную степнь // Проблемы кибернетики, вып. 2. — М.: Физматгиз, 1959. — С. 73-74.

6. Гашков С. Б. Замечание о минимизации глубины булевых схем // Вестник Московского университета. Сер. 1. Математика. Механика. — 2007. — № 6. — С. 7-9.

7. Гашков С. Б., Гашков И. Б. О сложности вычисления дифференциалов и градиентов // Дискретная математика. — 2005. — Т. 17, вып. 3. — С. 45-67.

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

9. Гашков С. Б., Сергеев И. С. О применении метода аддитивных цепочек к инвертированию в конечных полях // Дискретная математика. — 2006. — Т. 18, вып. 4. — С. 56-72.

10. Глухов М. М., Зубов А. Ю. О длинах симметрических и знакопеременных групп подстановок в различных системах образующих // Математические вопросы кибернетики, вып. 8. — М.: Наука, 1999. — С. 5-32.

11. Григорьев Д. Ю. Нижние оценки в алгебраической сложности вычислений // Теория сложности вычислений. I. — Записки научного семинара ЛОМИ. Т. 118. — JL: Наука, 1982. — С. 25-82.

12. Евдокимов А. А. Полные множества слов и их числовые характеристики // Методы дискретного анализа. — Новосибирск, 1983. — Вып. 39. — С. 7-19.

13. Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. — М.: Наука, 1982.

14. Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов // Проблемы кибернетики, вып. 38. — М.: Наука, 1981. — С. 117-179.

15. Кнут Д. Е. Искусство программирования для ЭВМ, т. 2. 1-е издание. — М.: Мир, 1977.

16. Кнут Д. Е. Искусство программирования, т. 2. 3-е издание. — М.: Издательский дом «Вильяме», 2000.

17. Коршунов А. Д. Об оценках сложности схем из объемных функциональных элементов // Проблемы кибернетики, вып. 19. — М.: Наука, 1967. — С. 275-284.

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

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

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

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

22. Кочергин В. В. Об аддитивных вычислениях систем целочисленных линейных форм // Вестник Московского университета. Сер. 1. Математика. Механика. — 1993. — № 6. — С. 97-101.

23. Кочергин В. В. О сложности вычислений в конечных абелевых, ниль-потентных и разрешимых группах // Дискретная математика. — Т. 5, вып. 1. — 1993. — С. 91-111.

24. Кочергин В. В. О сложности вычислений в конечных нильпотентных группах // Дискретный анализ и исследование операций. — 1996. — Т. 3, № 1. — С. 43-51.

25. Кочергин В. В. О сложности вычислений в некоторых классах групп // Второй сибирский конгресс по прикладной и индустриальной математике. Тезисы докладов, часть II. — Новосибирск, 1996. — С. 117-118.

26. Кочергин В. В. О некоторых оценках сложности вычисления систем одночленов // Труды II Международной конференции "Дискретные модели в теории управляющих систем" (23-28 июня 1997 г. — Москва: Диалог-МГУ, 1997. — С. 35-36.

27. Кочергин В. В. О сложности вычисления систем одночленов с ограничениями на степени переменных // Дискретная математика. — Т. 10, вып. 3. — 1998. — С. 27-34.

28. Кочергин В. В. О порядке роста сложности вычисления систем одночленов от многих переменных // Сибирская конференция по исследованию операций SCOR-98 (Новосибирск, 22-27 июня 1998 г). Материалы конференции. — Новосибирск, 1998. — С. 129.

29. Кочергин В. В. О сложности получения двоичных слов с заданным числом единиц схемами конкатенации // Труды III Международной конференции "Дискретные модели в теории управляющих систем" (22-27 июня 1998 г.). — Москва, Диалог-МГУ, 1998. — С. 58-62.

30. Кочергин В. В. О мультипликативной сложности двоичных слов с заданным числом единиц // Математические вопросы кибернетики, вып. 8. — М.: Наука, 1999. — С. 63-76.

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

32. Кочергин В. В. О некоторых обобщениях задачи об аддитивных цепочках // Дискретная математика и ее приложения. Сборник лекций. — М.: Изд-во Центра прикладных исследований при механико-математическом факультете МГУ, 2001. — С. 59-83.

33. Кочергин В. В. Об аддитивной сложности пар векторов длины 2 // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Пенза, 23-28 мая 2005 г.). — М.: Изд-во механико-математического факультета МГУ, 2005. -С. 74.

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

35. Кочергин В. В. Об асимптотике сложности аддитивных вычислений систем целочисленных линейных форм // Дискретный анализ и исследование операций. Серия 1. — 2006. — Т. 13, № 2. — С. 38-58.

36. Кочергин В. В. О сложности вычисления систем одночленов от двух переменных // Труды VII Международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта 2006 г.). — М.: МАКС Пресс, 2006. — С. 185-190.

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

38. Кочергин В. В. О максимальной сложности совместного вычисления систем элементов свободной абелевой группы // Вестник Московского университета. Сер. 1. Математика. Механика. — 2007, № 3. — С. 14-19.

39. Кочергин В. В. О сложности совместного вычисления трех элементов свободной абелевой группы с двумя образующими // Дискретный анализ и исследование операций. Серия 1. — 2008. — Т. 15, № 2. — С. 23-64.

40. Кочергин В. В. Замечание о сложности вычисления систем одночленов // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Казань, 2-7 июня 2008 г.). — Казань: Отечество, 2008. — С. 62.

41. Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики, вып. 19. — М.: Наука, 1967. — С.285-292.

42. Курош А. Г. Теория групп. — М.: Наука, 1967.

43. Ложкин С. А. О связи между глубиной и сложностью эквивалентных формул и о глубине монотонных функций алгебры логики // Проблемы кибернетики, вып. 38. — М.: Наука, 1981. — С. 269-271.

44. Лупанов О. Б. О вентильных и контактно-вентильных схемах // Доклады АН СССР. — 1956. — Т. 111, № 6. — С. 1171-1174.

45. Лупанов О. Б. Об одном методе синтеза схем // Известия вузов. Сер. Радиофизика. — 1958. — Т. 1, № 1. — С. 120-140.

46. Лупанов О. Б. О синтезе некоторых классов управляющих систем Ц Проблемы кибернетики, вып. 10. — М.: Физматгиз, 1963. — С 63-97.

47. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики, вып. 14. — М.: Наука, 1965. — С. 31-110.

48. Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23. — М.: Наука, 1970. — С. 4381.

49. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во Московского университета, 1984.

50. Мерекин Ю. В. Нижние оценки мультипликативной сложности символьных последовательностей, определяемых монотонными симметрическими булевыми функциями // Дискретный анализ и исследование операций. Сер. 1. — 1999. — Т. 6, № 3. — С. 3-9.

51. Мерекин Ю. В. Нижняя оценка сложности для схем конкатенации слов // Дискретный анализ и исследование операций. — 1996. — Т. 3, № 1. — С. 52-56.

52. Мерекин Ю. В. О порождении слов с использованием операции композиции // Дискретный анализ и исследование операций. — 2003. — Т. 10, № 4. — С. 70-78.

53. Мерекин Ю. В. Об аддитивной сложности частично коммутативных слов // Дискретный анализ и исследование операций. Сер. 1.— 2005. — Т. 12, № 4. — С. 40-50.

54. Мерекин Ю. В. Оценки мультипликативной сложности двоичных слов, определяемых поясковыми булевыми функциями // Дискретный анализ и исследование операций. Сер 1. — 2002. — Т. 9, № 2. — С. 36-47.

55. Нечипорук Э. И. О сложности схем в некоторых базисах, содержащих нетривиальные элементы с нулевыми весами // Проблемы кибернетики, вып. 8. — М.: Физматгиз, 1962. — С. 123-160.

56. Нечипорук Э. И. О вентильных схемах // Доклады АН СССР. — 1963. — Т. 148, № 1. — С. 50-53.

57. Нечипорук Э. И. О синтезе логических сетей в неполных и вырожденных базисах // Проблемы кибернетики, вып. 14. — М.: Наука, 1968. — С. 111-160.

58. Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики, вып. 21. — М.: Наука, 1969. — С. 5102.

59. Олег Борисович Лупанов (к шестидесятилетию со дня рождения) // Методы дискретного анализа в теории графов и сложности. — Новосибирск, 1992. — Вып. 52. — С. 3-14.

60. Орлов В. А. Реализация «узких» матриц вентильными схемами // Проблемы кибернетики, вып. 22. М.: Наука, 1970. — С 45-52.

61. Потапов В. Н. Аддитивная сложность слов с ограничениями на состав подслов // Дискретный анализ и исследование операций. Сер. 1. — 2004. — Т. 11, № 1. — С. 52-78.

62. Потапов В. Н. О максимальной длине двоичных слов с ограниченной частотой единиц и без одинаковых подслов заданной длины // Дискретный анализ и исследование операций. Сер. 1. — 2004. — Т. 11, № 3. — С. 48-58.

63. Сэвидж Д. Е. Сложность вычислений. — М.: Изд.-во «Факториал». — 1998.

64. Сергеев И. С. О сложности градиента рациональной функции // Дискретный анализ и исследование операций. Сер. 1. — 2007. — Т. 14, № 4. — С. 57-75.

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

66. Слисенко А. О. Сложностные задачи теории вычислений // Успехи математических наук. — 1981. — Т. 36, вып. 6. — С. 21-103.

67. Храпченко В. М. Нижние оценки сложности схем из функциональных элементов // Кибернетический сборник. Новая серия. Вып. 21. — М.: Мир, 1984. — С. 3-54.

68. Чашкин А. В. О сложности булевых матриц, графов и соответствующих им булевых фуекций // Дискретная математика. — 1994. — Т. 6, вып. 2. — С. 44-73.

69. Ширшов А. И. Некоторые алгоритмические проблемы для алгебр Ли // Сибирский математический журнал. — 1962. — Т. 3, № 2. — С. 292-296.

70. Шоломов Л. А. О функционалах сложности, характеризующих сложность систем недоопределенных булевых функций // Проблемы кибернетики, вып. 19. — М.: Наука, 1967. — С. 123-140.

71. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, вып. 2. — М.: Физ-матгиз, 1959. — С. 75-121.

72. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.

73. Althôfer I. Tight lower bounds on the length of word chains // Inform. Process. Lett. — 1990. — V. 34, № 5. — P. 275-276.

74. Arnold A., Brlek S. Optimal word chains for the Thue-Morse word // Inform, and Comput. — 1989. — V. 83, № 2. — P. 140-151.

75. Bellman R. E. Addition chains of vectors (Advanced problem 5125) // Amer. Math. Monthly. — 1963. — V. 70. — P. 765.

76. Bergeron F., Berstel J., Brlek S., Duboc C. Addition chains using continued fractions // Journal of Algorithms. — 1989. — V. 10, № 3. — P. 403-412.

77. Bernstein D. J. Pippenger's exponentiation algorithm // Available at : http://cr.yp.to/papers/pippenger.pdf. — 2002.

78. Bernstein D. J. The transposition principle // Available at : http://cr.yp.to/transposition.html. — 2004.

79. Berstel J., Brlek S. On the lenght of word chains // Inform. Process. Lett. — 1987. — V. 26, № 1. — P. 23-28.

80. Bosma W. Signed bits and fast exponentiation // Journal de Théorie des Nombres de Bordeaux. — 2001. — V. 13. — P. 27-41.

81. Bostan A., Lecerf G., Schost E. Tellegen's principle into practice // IS-SAC Conf. (Philadelphia), 2003 . — Philadelphia: ACM Press, 2003. — P. 37-44.

82. Bos J., Coster M. Addition chain heuristics // Proceedings of Cryp-¿o'89. — Springer-Verlag, 1990. — V. 435. — P. 400-407.

83. Bousquet-Mélou M. The number of minimal word chains computing the Thue-Morse word // Inform. Process. Lett — 1992. — V. 44, № 2. — P. 57-64.

84. Brauer A. On addition chains // Bull. Amer. Math. Soc. — 1939. — V. 45. — P. 736-739.

85. Brickell E. F., Gordon D. M., McCurley K. S., Wilson D. B. Fast exponentiation with precomputation: algorithms and lower bounds. — Preprint, 1995.

86. Brickell E. F., Gordon D. M., McCurley K. S., Wilson D. B. Fast exponentiation with precomputation. // Proceedings of Eurocrypf 92. — Springer-Verlag, 1992. — V. 658. — P. 200-207.

87. Byrne A., Meloni N., Crowe F., Marnane W. P., Tisserand A., Popovici E. M. SPA resistant elliptic curve cryptosystem using addition chains // International Conference on Information Technology-ITNCQ7. — 2007. — P. 995-1000.

88. Coster M. J. Some algorithms on addition chains and their complexity. — CWI Report CS-R9024, 1990.

89. Datta B., Singh A. N. History of Hindi Mathematics. — Bombay, 1935.

90. Diwan A. A. A new combinatorial complexity measure for languages. — Tata Institute. Bombay, India. — 1986.

91. Dobkin D., Lipton R. J. Addition chain methods for the evaluation of specific polynomials // SI AM J. Comput. — 1980. — V. 9, N 1. — P. 121-125.

92. Eisentrager K, Lauter K., Montgomery P. L. Fast elliptic curve arithmetic and improved Weil Pairings evaluation // Proceedings of RSA-CT 2003.

93. Elias M., Neri F. A note on addition chains and some related conjectures // Sequences. Editor R. M. Capocelli. — Springer-Verlag, 1990. — P. 166-181.

94. Erdos P. Remarks on number theory, III: On addition chains // Acta Arith. — 1960. — V. 6. — P. 77-81.

95. Fiduccia C. M. On the algebraic complexity of matrix multiplication. — Brown university, Providence, 1973.

96. Gordon D. M. A survey of fast exponentiation methods // Journal of Algorithms. — 1998. — V. 27. — P. 129-146.

97. Goundar R. R., Shiota K., Toyonaga M. New strategy for doubling-free short addition-subtraction chain // International Journal of Applied Mathematics. — 2007. — V. 2, № 3.

98. Graham R. L., Yao A. C.-C., Yao F.-F. Addition chains with multiplicative cost // Discrete Math. — 1978. — V. 23. — P. 115-119.

99. Hebb K. R. Some results on addition chains // Notices of the American Mathematical Society. — 1974. — V. 21. — P. A-294.

100. Kaltofen E., Shoup V. Subquadratic-time factoring of polynomials over finite fields // Math. Comput. — 1998. — V. 67, № 223. — P. 1179-1197.

101. Kaminski M., Kirkpatrick D., Bshouty N. Addition requirements for matrix and transposed matrix products // Journal of Algorithms. — 1988. — T. 9, № 3. — C. 354-364.

102. Knuth D. E., Papadimitriou C. H. Duality in addition chains // Bulletin of the European association for Theoretical Computer Science. — 1981. — V. 13. — P. 2-4.

103. Kobayashi K., Morita H., Hakuta M. Multi scalar-multiplication algorithm over elliptic curve // IEICE Transactions on Information and Systems. — 2001. — V. E84-D, № 2. — P. 271-276.

104. Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation. — 1987. — V. 48 (177). — P. 203-209.

105. Koyama K., Tsuruoka Y. A signed binary window method for fast computing over elliptic curves // IEICE Trans. Fundamentals. — 1993. — V. E76-A. — P. 55-62.

106. Kunihiro N., Yamamoto H. Window and extended window methods for addition chain and addition-subtraction chain // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 1998. — V. E81-A, № 1. — P. 72-81.

107. Kunihiro N., Yamamoto H. New method for generating short addition chains // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 2000. — V. E83-A, № 1. — P. 60-66.

108. Kweon K., Hong S.-M., Oh S.-Y., Yoon H. Finding shorter addition/subtraction-chains // CCCT'05 (International Conference on Computing, Communications and Control Technologies). — http: //hdl.handle.net /10203/447

109. McCarthy D. P. Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains // Math. Comp. — 1976. — V. 46. — P. 603-608.

110. McCarthy D. P. The optimal algorithm to evaluate xn using elementary multiplication methods // Math. Comp. — 1977. — V. 31 (137). — P. 251-256.

111. McColl W. F., Paterson M. S. The depth of all Boolean functions // S I AM J. Comput. — 1977. — V. 6, № 2. — P. 373-380.

112. Merekin Yu. V. Some bounds on the complexity of words // Southeast Asian Bulletin of Mathematics. — 2006. — V. 30. — P. 1081-1121.

113. Morain F., Olivos J. Speeding up the computation on an eliptic curve using addition-subsraction chains // Informatique Théorique et Applications. — 1990. — V. 24. — P. 531-544.

114. Morgenstern J. Note on a lower bound of the linear complexity of the fast Fourier transform // J. Assoc. Comput. Mach. — 1973. — V. 20. — P. 305-306.

115. Morgenstern J. On linear algorithms // Theory of machines and computations. — New York, 1971. — P. 59-66.

116. Nedjah N., Mourelle L. Minimal addition-subtraction chains using genetic algorithm // Advances in Information Systems. Lecture Notes in Computer Science. — 2002. — V. 2457. — P. 303-313.

117. Olivos J. On vectorial addition chains //J. Algorithms. — 1981. — V. 2, N 1. — P. 13-21.

118. Pippenger N. On evaluation of powers and related problems // Proc. 17th Ann. IEEE Symp. on Found, of Computer Sci. (Houston, TX, 25-27 Oct. 1976.) — P. 258-263.

119. Pippenger N. On evaluation of powers and monomials // SIAM J. Corn-put. — 1980. — V. 9, N 2. — P. 230-250.

120. Pippenger N. The mimimum number of edges in graphs with prescribed paths // Math. Systems Theory. — 1979. — V. 12, № 4. — P. 325-346.

121. Savage J. E. An algorithm for the computation of linear forms // SIAM J. Comput. — 1974. — V. 3, № 2. — P. 150-158.

122. Scholz A. Jahresbericht // Deutsche Mathematiker- Vereinigung. — 1937. — V. 47. — P. 41-42.

123. Schonhage A. A lower bound for the lenght of addition chains // Theoretical Computer Science. — 1975. — V. 1. — P. 1-12.

124. Shannon С. E. The synthesis of two-terminal switching circuits // Bell Syst. Techn. J. — 1949. — V. 28, № 1. — P. 59-98. (Русский перевод: Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ, 1963. — С. 59-101.)

125. Southard Т. Н. Addition chains for the first N squares // Tech. Rep. CNA-84, Univ. of Texas at Austin, 1974.

126. Strassen V. Berechnungen in partiellen Algebren endlichen Typs // Computing. —1973. — V. 11. — P. 181-196.

127. Straus E. G. Addition chains of vectors // Amer. Math. Monthly. — 1964. — V. 71. — P. 806-808.

128. Subbarao M. V. Addition chains — some results and problems // Number Theory and Applications. Editor R. A. Mollin. NATO Advanced Science Institutes Series: Series C. — Kluwer Academic Publisher Group, 1989. — V. 265. — P. 555-574.

129. Thurber E. G. The Scholz — Brauer problem on addition chains // Pacific Journal of Mathematics. — 1973. — V. 40. — P. 229-242.

130. Thurber E. G. Addition chains — an erratic sequence // Discrete Mathematics. — 1993. — V. 122. — P. 287-305.

131. Thurber E. G. Efficient generation of minimal length addition chains // SI AM Journal of Computing. — 1999. — V. 28. — P. 1247-1263.

132. Toundar R. R., Shiota K., Toyonaga M. New strategy for doubling-free short addition-substruction chain // International Journal of Applied Mathematics. — 2007. — V. 2, № 3.

133. Tsai Y., Chin Y. A study of some addition chain problems // Intern. J. Computer Math. — 1987. — V. 22. — P. 117-134.

134. Vassiliev N. N. Complexity of monomial evaluations and duality // Computer algebra in scientific computing — CASC99 (Munich). — Berlin: Springer, 1999. — P. 479-484.

135. Volger H. Some results on addition/subtraction chains // Information Processing Letters. — 1985. — V. 20. — P. 155-160.

136. Walter C. D. Exponentiation using division chains // IEEE Transactions on Computers. — 1998. — V. 47 (7). — P. 757-765.

137. Yacobi Y. Exponentiating faster with addition chains // Eurocryptf 90. — 1991. — P. 222-229.

138. Yao A. C.-C. On the evaluation of powers // SIAM J. Comput. — 1976. — V. 5. — P. 100-103.