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

• Кочергин, Вадим Васильевич
• доктор физико-математических наук
• 2008

Оглавление диссертации доктор физико-математических наук Кочергин, Вадим Васильевич

Введение

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.

Список литературы диссертационного исследования доктор физико-математических наук Кочергин, Вадим Васильевич, 2008 год

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.