Верхние и нижние оценки на схемную сложность явно заданных булевых функций тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Деменков, Евгений Александрович

• Деменков, Евгений Александрович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Деменков, Евгений Александрович

Оглавление

Введение

1 Определения и результаты

1.1 Схемная сложность

1.2 Методы доказательств оценок на схемную сложность, использующиеся в работе

1.2.1 Метод элиминации элементов

1.2.2 Метод подсчета элементов

1.2.3 Метод предкодирования

1.3 Результаты

1.3.1 Известные результаты в схемной сложности

1.3.2 Полученные результаты

2 Верхние оценки

2.1 Верхняя оценка 4.5п на функцию, вычисляющую сумму входных битов

2.2 Верхняя оценка на АЬЬМОБ

3 Нижние оценки

3.1 Нижняя оценка 3п — о{п) для аффинного дисперсера

3.2 Нижняя оценка на вектор из п функций в базисе V2 ■ ■

Литература

Введение диссертации (часть автореферата) на тему «Верхние и нижние оценки на схемную сложность явно заданных булевых функций»

Введение

Теория сложности

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

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

Схемная сложность

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

Изучение булевых схем можно найти ещё в работах Шеннона [1]. Они активно изучались советскими математиками с 1950-х годах. Обозначим через С(п) функцию Шеннона для схем — максимальный размер минимальной схемы, вычисляющей функцию от п переменных. Поскольку любую булеву функцию можно вычислить с помощью конъюнктивной нормальный формулы, то С(п) можно оценить сверху через 0(п2п). Шеннон в 1949 году [1] показал, что для любого б и достаточно большого п верно неравенство С(п) > (1 — е)2п/п. В 1956 году Миллер доказал для любого конечного базиса верхнюю оценку С(п) = 0(2п/п) [2]. В 1958 году Лупанов [3] показал, что С(п) < (1 + схп)2п/п, где ап = 0(\ogn/n). Таким образом, мы знаем, что большинство функций от п переменных имеют схемную сложность 0,(2п/п). Тем не менее, задача построения явно заданной буле-

вой функции высокой схемной сложности оказалась очень трудной. На сегодняшний день наилучшей нижней оценкой для явно заданной булевой функции является оценка 3п — о(п), доказанная Блюмом в 1984 году [4] (подробный обзор известных нижних оценок на схемы без ограничений приведён в разделе 1.3.1).

Булеву функцию принято (см., например, [5, 6]) называть явно заданной, если прообраз единицы этой функции лежит в классе NP. Более формально, в данной работе под булевой функцией / мы понимаем бесконечное семейство функций {/¿: г е М}, где /¿: {0,1}г —У {0,1}. Такая функция называется явно заданной, если и^к/ГЧЦ € №.

Схемы с ограничениями

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

Монотонные схемы

Одной из таких моделей являются монотонные схемы. В таких схемах используются только элементы, вычисляющие конъюнкцию и дизъюнкцию. Они также называются схемами без отрицания. Функции, которые можно вычислить с помощью таких схем, называются монотонными. До 1984 года была известна только линейная ниж-

няя оценка для таких схем. В 1985 году Андреев [7] и Разборов [8] независимо совершили прорыв в данной области, получив суперполиномиальные нижние оценки.

Формулы

Другим классом являются схемы, у которых исходящая степень вершин не превосходит 1. Такие схемы называются формулами. Легко видеть, что соответствующий формуле граф является деревом. Под сложностью формулы понимают обычно количество листьев. Риор-дан и Шэнон в 1942 [9] показали, что для вычисления большинства функций требуются формулы размера порядка 2П/ log п. Поскольку каждая вершина имеет не более одного потомка, многие вершины могут вычислять одинаковые функции. Из-за этого размер формулы может превосходить размер схемы многократно.

Чаще всего рассматривают формулы над базисом из конъюнкции, дизъюнкции и отрицания. За счёт законов де Моргана -¡(хАу) = (-■гг)) V (-1 у) и -л(xV у) = (~>х) А можно считать, что все отрицания стоят возле переменных. Такие формулы называются формулами де Моргана. Аналогично можно определить схемы де Моргана. Можно легко показать, что любая схема над базисом, состоящим из {Л, V, ->} может быть приведена к схеме де Моргана с не более чем удвоением числа вершин.

Для формул удаётся связать оптимальные размер и глубину. Обо-

значим через !/(/) минимальное количество листьев, а через £)(/) — минимальную глубину для формул де Моргана, вычисляющих /. Очевидно, что £>(/) > !/(/). Храиченко в 1978 году [10] показал, что верно и обратное неравенство: £>(/) < 1.73 • к^2£(/).

Наилучшей известной нижней оценкой на сложность формул де Моргана является оценка п3~0^. Этот результат был получен Хаста-дом в 1998 году [И]. До этого был ряд других результатов:

• Субботовская в 1961 году первой получила нетривиальную оценку П(п3/2) [12].

• В 1971 году она была улучшена Храпченко до 0,(п2) [13].

• Андреев улучшил эту оценку до П(п2,5) в 1985 году [7].

• В 1993 году Импальяцо и Ниссан получили оценку П(п2-55) [14].

• В 1993 году Патерсон и Цвик доказали оценку Г2(п2'63) [15].

Для полного бинарного базиса наилучшей известной нижней оценкой но-прежнему является оценка 0,(п2/\ogri), доказанная Нечипоруком в 1966 годму [16]

Схемы ограниченной глубины

Ещё одно естественное ограничение — это ограничение на глубину схемы. Если глубина схемы ограничена константой, то разумно считать, что входящая степень элементов схемы не ограничена (ина-

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

Для схем глубины ¿>3 нижние оценки доказываются уже сложнее. Обозначим через Ь^п) и С^(п) функции Шеннона для формул и схем неограниченной входящей степени глубины (1. Легко показать, что Ь2{п) = п2п. Лупанов [17, 18] показал, что схемы и формулы глубины 3 не слабее схем глубины (1 > 3:

Ьй(п) ~ Ь3(п) ~ 2П/ \ogri,

Сл{п) ~ С3(п) ~ 2П/п.

Хастад, Юкна и Пудлак показали [19], что любая схема глубины 3, вычисляющая функцию голосования (Ма^гсх,..., хп) = 1 х\ + ... + хп > \п/2\) имеет размер не меньше

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

Вегенера [5] и Юкны [6].

Глава 1

Определения и результаты

1.1 Схемная сложность

Через Вщт обозначим множество всех булевых функций /: {0,1}п —{0,1}т. Впд обозначается через Вп. Функция / G Вп называется симметрической, если её значение зависит только от суммы входных битов. Другими словами, должен существовать вектор v £ {0,1}п+1 (называемый вектором значений /), такой что f(xi,...,xn) = vs, где s = Yli<i<nxi■ Фундаментальные симметрические функции EX, ТН и MOD определяются следующим

образом:

ЕХ%(хи ...,хп) = 1 ^ х{ = к,

1<г<п

1<г<п

МОБ^Дгсь ..., хп) = 1 ^ х{ = г (шос! т).

1<г<п

Схемой называется ациклический ориентированный граф, все вершины которого имеют входящую степень 0 или 2. Вершины входящей степени 0 помечены переменными из множества {х\,... ,хп} и называются входами . Вершины входящей степени 2 помечены функциями из £?2 и называются элементами . Будем говорить, что вершины, помеченные переменным, вычисляют эти переменные. А вершины помеченные функциями, вычисляют эти функции от своих родителей. Также есть т специально выделенных выходных элементов . Таким образом, схема вычисляет функцию из Вщт. Пример схемы приведён на рисунке 1.1 . Размер схемы — это количество элементов в ней. Через С(/) мы обозначаем минимальный размер схемы, вычисляющей /.

Всего существуют 16 различных бинарных функций:

• 2 константных функции — значение которых не зависят от входных значений.

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

Рис. 1.1: Пример схемы.

• 2 функции типа ф — они вычисляют функции вида х Ф у ф а, где а е {0,1}.

• 8 функции типа Л — они вычисляют функции вида (х ф а) Л (у Ф Ь) ф с, где а,Ь,се {0,1}.

Два наиболее часто рассматриваемых базиса — это полный бинарный базис В2 и базис £/2 = \ {ф, =}.

с

1.2 Методы доказательств оценок на схемную сложность, использующиеся в работе

Методов доказательств новых оценок известно немного. В данной работе рассматриваются три. Два метода доказательства нижних оце-

нок и один — верхних.

1.2.1 Метод элиминации элементов

Самым распространённым методом доказательства нижних оценок на размер схем без ограничений является метод элиминации элементов. Его основная идея заключается в следующем. Предположим, мы хотим доказать нижнюю оценку ап —0(1) для некоторого класса функций Т. Рассмотрим функцию / из этого класса. И пусть С — схема минимального размера, вычисляющая /. Предположим, что после подстановки в значений к переменным получается функция /', лежащая в классе Т (это необходимо для того, чтобы доказывать оценку по индукции). И пусть на основе С можно построить схему, вычисляющую размер которой меньше С как минимум на ак элементов. Если такую операцию можно произвести с произвольной функцией, зависящей как минимум от т = 0( 1) переменных, то повторив такую операцию несколько раз и получив функцию, которая зависит меньше, чем от т = 0( 1) переменных, мы получим схему, которая меньше исходной на а(п — т) = ап — 0(1). А значит, исходная схема имела размер не меньше ап — 0(1).

Рассмотрим в качестве примера схему на рисунке 1.2.

После подстановки гс2 = 1 элемент будет вычислять непосредственно -1^1. А элемент <32 будет вычислять константу 1. Тогда также будет вычислять константу 1. (24 в свою очередь будет вы-

Рис. 1.2: Схема до подстановки.

числять х\ = хз, а Сб будет равен (^4. Значит, можно перестроить схему. И схема на рисунке 1.3 будет вычислять то же самое, что и схема 1.2 после подстановки, но иметь размер на 4 элемента меньше.

Рис. 1.3: Схема после подстановки

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

1.2.2 Метод подсчета элементов

Другой способ доказательства нижних оценок используется для функций с несколькими выходами. Рассмотрим некоторую функцию / : {0,1}п —> {0,1}т, вычисляющую т различных функций (/^ ф /_,• и ф /• для всех г ф э). Ламаньея и Сэвиджем в 1973 году [20] доказали следующую нижнюю оценку:

Сп(/)> тт СоШ + т-1.

1 <г<т

Другими словами, для вычисления схемой этой функции, понадобится хотя бы т — 1 дополнительных элементов. В разделе 3.2 мы усилим данную оценку для базиса и^-

Этим метод был представлен : Им мы воспользуемся в главе 3.2.

1.2.3 Метод предкодирования

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

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

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

1.3 Результаты

1.3.1 Известные результаты в схемной сложности

Шенноном показал в 1949 году [1], что из простых мощностных соображений следует, что схемная сложность практически любой функции не меньше 0(2п/п). Но до сих пор неизвестно ни одной суперлинейной оценки для явно заданной булевой функции.

Нижнюю оценку п—1 можно получить следующим образом. Если функция / существенно зависит от п переменных (то есть для любой переменной г подфункции /\Хг=о и /|х,=1 различны), то С(/) > п— 1. Действительно, пусть С — минимальная схема, вычисляющая /, и пусть в ней к элементов. Тогда суммарная исходящая степень не меньше к + п — 1 (все переменные и все элементы, кроме элемента, вычисляющего саму функцию, имеют исходящую степень не меньше 1). Суммарная входящая степень равна удвоенному количеству элементов, то ечть 2к. Поскольку эти степени совпадают, получаем 2к > к + п — 1 или к > п — 1.

Также известны следующие более сильные линейные оценки на схемную сложность в базисе В2.

• В 1965 году Клосс и Малышев доказали нижнюю оценку 2п — 0(1) [21].

• Шнор в 1974 году доказал нижнюю оценку 2п — 0(1) для широкого класса функций [22].

• В 1977 году доказал нижние оценки 2п — 0(1) и 2.5п — 0(1) для функции индексации и некоторой её модификации [23].

• В 1976 году Стокмайер доказал нижнюю оценку 2.5п — 0(1) для почти всех симметрических функций [24].

• В 1983 году Блюмом была доказана рекордная на данный момент нижняя оценка 3п — о(п) [4].

Для базиса известны более сильные нижние оценки.

• В 1974 году Шнор доказал, что функция чётности имеет сложность 3(п - 1) [22].

• Цвик в 1991 году привёл доказательство нижней оценки 4п — 0(1) для некоторых симметрических функций [25].

• Лахич и Раз в 2001 году доказали нижнюю оценку 4.5п — о(п) для так называемой /с-смешанной функции [26].

• В 2002 году Ивама и Морицуми улучшили оценку до Ъп — о(п) для того же класса функций [27]. Данная оценка является на сегодняшний день самой сильной из известных.

• В 2012 году Куликов, Меланич и Михайлин получили значительно более простое доказательство оценки 5п — о(п) для одновременного вычисления нескольких линейных функций [28].

Нелинейных нижних оценок неизвестно и для функций из ВПуП. Опять же, из мощностных соображений и используя оценки Лупа-нова, можно доказать, что схемная сложность практически любой функции из Вщп есть 6(2П).

С помощью метода Ламаньи и Сэвэджа [20] легко получить нижние оценки 4п — о{п) и 6п — о{п) на схемную сложность над В2 и 112 соответственно для функций из В™. Эти оценки выводятся из оценок для функций из Вп и явлюятся самыми сильными из известных. Редькин [29] доказал, что схемная сложность над В2 бинарного сумматора есть 2.5п — 3 (бинарный сумматор — это функция из Вп^п/2+1, которая вычисляет сумму двух входных п/2-битовых чисел). Хильтген [30] изучал так называемые слабо односторонние функции (обратимые функции / из Вп^п, такие что С(/) < С(/-1)). Он построил примеры таких /, для которых Св2{}) = п — ©(1) и

сВ2(г1) = 2п-е(1).

1.3.2 Полученные результаты

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

классическую оценку 5n + o(n), доказанную Лупановым в 1965 году [31]. Результат опубликован в журнале Information Processing Letters в 2010 году [32].

Следующим результатом второй главы является почти линейная верхняя оценка на схемную сложность одновременного вычисления всех MOD-функций. Несложно показать, что для почти всех наборов из п симметрических функций схемная сложность почти квадратична — ö(n2/ logn). Ни одного такого явного'набора, однако, неизвестно. Известно в то же время, что для одновременного вычисления всех функций ЕХ и ТН достаточно схем линейного размера. Мы усиливаем данный результат, доказывая, что и все MOD-функции можно вычислить схемами почти линейного размера. Результат представлен на международной конференции Computer Science in Russia в 2012 году и входит в труды конференции [33].

В третьей главе доказываются новые нижние оценки. Первым результатом является рекордная известная оценка 3п — о(п) на схемную сложность явной заданной булевой функции в базисе Данная оценка повторяет оценку, доказанную Блюмом в 1983 году [4], но доказывается значительно проще. В частности, доказательство почти не содержит разбора случаев. В то же время для доказательства понадобилась более сложная булева функция — так называемый аффинный дисперсер, явная конструкция которого была представлена только в 2009 года Бен-Сассоном и Коппарти [34]. Данный резуль-

тат был представлен на международной конференции Mathematical Foundations of Computer Science в 2012 году и входит в труды конференции [35]. Отдельный интерес представляет то, что в данном доказательстве, в отличие от предыдущих доказательств, основанных на методе элиминации элементов, используются подстановки линейных функций.

Заключительным результатом диссертации является нижняя оценка 7п — о(п) на схемную сложность в базисе U^ функции из Вщп. Это улучшает предыдущую известную оценку бп — о(п), получающуюся применением метода Ламаньи и Сэвэджа к оценке Ъп — о(п), доказанной Ивамой и Морицуми. Данный результат был представлен на международной конференции Computer Science in Russia в 2012 году и входит в труды конференции [36]. В отличие от метода элиминации элементов, использующемся в доказательстве предыдущей оценки, здесь анализируется часть схемы у выходов, а не входов.

Глава 2

Верхние оценки

2.1 Верхняя оценка А.Ъп на функцию, вычисляющую сумму входных битов

Функция / € Вп называется симметрической, если для любой перестановки а € Бп и переменных х\,...,хп • • ■, хп) — /(ха(1 )> • • •; ха(п))- Такие функций всегда представляли особый интерес в алгебре. Ещё в 1938 году Шеннон выделил симметрические булевы функции в отдельный класс булевых функций [37]. Этот класс содержит в себе много важных функций, для которых известно множество оценок на сложность в различных моделях вычислений (напомним, что через ¡¡и Ьц мы обозначаем соответственно схемную и формульную сложность над базисом С

• Функция чётности: •••, хп) — xi © • • • © хп

- Ьи2{@п) < |п2 (Яблонский, 1954 [38])

- Ьи2{®п) > п3/2 (Субботовская, 1961 [12])

- Ьи2(фп) = @(п2) (Храпченко, 1971 [13])

- Си2{@п) = Зп - 3 (Шнорр, 1976 [39])

• Пороговая функция: ТЩ(х1,..., хп) = 1 х\ + ... + хп> к

- Ьи2(ТЩ) > |log2n (Кричевский, 1961 [40])

- Ьи2{ТЩ) < nLlog2nJ (Ложкин, 2005 [41])

- Ьи2(ТЩ) >к(п-к + 1) (Храпченко, 1971 [13])

- Ьв2(ТЩ) < гг3-13 (Патерсон, Пиппенгер и Цвик, 1990 [42])

- Ьв2(ТЩ) > nlnlnn (Пудлак, 1984 [43])

• Функция голосования: MAJn(:ri,..., хп) = х\ + .. .+хп > \п/2]

- Ьв2{Majn) >: nlnn (Фишер, Майер и Патерсон, 1982 [44])

- Ьв2{Majn) ■< n4-57 (Патерсон и Цвик, 1993 [15])

• Функция делимости: MOD£(zi,... ,хп) = х\ + ... + хп = 0 (mod к). О них мы более подробно поговорим в разделе 2.2

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

только от суммы входов, то есть от количества переменных, принимающих значение 1. Поэтому для их вычисления достаточно знать значения [log п + 1] функций, кодирующих сумму входных битов.

Для построения схемы мы воспользуемся идей предкодирования, предложенной Лупановым [3]. Чтобы вычислить произвольную симметрическую функцию, мы научимся эффективно вычислять сумму входных п битов. По данной сумме значение любой симметрической функции восстанавливается за о(п).

Основным блоком схемы, предложенной Лупановым, является сумматор FA: {О, I}3 —» {О, I}2. Блок FA(x,y,z) = (sum, carry) кодирует сумму х, у, z таким образом, что sum = х ф у 0 z вычисляет остаток суммы по модулю 2, a carry = ху ф yz ф zx является битом переноса (х + у + z — sum + 2 • carry) Известно, что для реализации такого сумматора необходимо 5 элементов. Пример такого сумматора показан на рисунке 2.1

Интересующую нас схему можно построить на основе сумматоров, как показано на рисунке 2.2. При этом X^Li = Ур?-Но такой сумматор не является минимальным, если рассматривать другие способы кодирования суммы. На рисунке 2.3 представлен сумматор {О, I}3 {О, I}2 размера 4. В данном случае х + у + -г = 2 • (щ ф и0) + щ.

1 Чтобы различать сложение в Z и сложения в Z2, для перового будем использовать символ

+, а для второго ф.

1_i

FA

вит

Vit/

вит

carry

carry

Рис. 2.1: Схема, реализующая сумматор. Х\Х2 ХЪХЬ ХП

Рис. 2.2: Схема на основе сумматоров.

Данный блок был использован Стокмайером [24] для доказательства верхней оценки 2.5п +0(1) на Св2 (МОБ"). Сформулированный ниже основной результат данного раздела обобщает идеи Стокмайе-ра.

Теорема 1. Любая симметрическая булева функция от п переменных моэюет быть вычислена схемой размера 4.5п + о(п).

Основным блоком конструкции является двойной сумматор

Рис. 2.3: Сумматор меньшего размера.

MDFA, полученный соединением двух блоков FA и изменением кодировки. За счёт изменения кодировки его размер равен не десяти (как при непосредственном соединении двух FA), а восьми. На вход он получает 5 значений z, xi,xi®x2, жз, х^фх^ На выходе он выдаёт carryi, carryi ф carry2, sum. При этом:

z + х 1 + #2 + ж3 + = 2 • (carryi + carry2) + sum

carryi = xiyi Ф yiz ф zx 1

carry2 = Х2У2 Ф 2/2(2 ФЖ1Ф yi) Ф (z ф xx Ф yi)x2 = zy2 Ф zx2 ф Х1У2 Ф X1X2 Ф 2/12/2 Ф У1Х2 ф Х2У2

Схема, реализующая его, представлена на рисунке 2.4 2.

2Отрицание на ребре подразумевает, что элемент gj вычисляет бинарную функцию л, такую что вторая переменная входит со знаком отрицания.

Рис. 2.4: Схема, реализующая уменьшенный двойной сумматор.

Элементы в этом блоке вычисляют следующие функции:

9i = xi® zygz = xi®yi® г,дъ = xi®yi@ z®x2, Я2 = (x1@y1)V(xi®z) = y1®z@(x1eyi)(xi®z) = = xiUi ® Viz © ZX\ Ф x\ ф У\ Ф z = carryi ф^ф^фг,

g± = g2®gs = 92®x\@yi®z = carryu

gs = xi®yi®z®x2,

96 = gz ф x2 ф У2 = Ф У1 Ф X2 Ф y2 Ф Z = sum,

gi = д5(х2®У2®1) = (xi®yi® Z®x2){x2®y2®l) =

= ф У1 Ф Z Ф хгх2 Ф У1Х2 Ф zx2 Ф Х1У2 Ф У1У2 Ф zy2 ф Х2У2 =

= xi ф У\ Ф ^ ф carry2,

98 = g2 Ф gi = carryi ф carry2.

Корректность схемы можно также проверить с помощью таблицы истинности (таблица 2.1).

Доказательство теоремы 1. Поскольку любая симметрическая функция однозначно определятся суммой входов, то для любой симметрической функции / : {0,1}п {0,1} существует функция /г : {0,1}1о§п {0,1} такая, что

п [к^п+1]

Из результата Лупанова следует, что для вычисления такой

На основе двойного сумматора можно построить схему, как показано на рисунке 2.5, которая будет вычислять г/о,..., 2/fiogn+i] •

Эта схема состоит из [п/4] + \п/8 \ +... = п/2 + о(п) MDFA блоков и [п/2] дополнительных 0 элементов. Размер каждого MDFA блока равен восьми. Размер всей схемы равен 8 • п/2 + о(п) + п/2 = 4.5 • п + о(п). □

функции достаточно О, (2logn+1/(log n + 1)) = о(п) элементов.

Таблица 2.1: Таблица истинности элементов

XI У1 Х2 У2 г вит 51 92 9з 94 95 96 97 98

0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 1 1 0 1 1 1 0

0 0 0 1 0 1 0 0 0 0 0 1 0 0

0 0 0 1 1 2 1 1 1 0 1 0 0 1

0 1 0 0 0 1 0 1 1 0 1 1 1 0

0 1 0 0 1 2 1 1 0 1 0 0 0 1

0 1 0 1 0 2 0 1 1 0 1 0 0 1

0 1 0 1 1 3 1 1 0 1 0 1 0 1

0 0 1 0 0 1 0 0 0 1 1 0

0 0 1 0 1 2 1 1 1 0 0 0 0 1

0 0 1 1 0 2 0 0 0 1 0 1 1

0 0 1 1 1 3 1 1 1 0 0 1 0 1

0 1 1 0 0 2 0 1 1 0 0 0 0 1

0 1 1 0 1 3 1 1 0 1 1 1 0 1

0 1 1 1 0 3 0 1 1 0 0 1 0 1

0 1 1 1 1 4 1 1 0 1 1 0 1

1 0 0 0 0 1 1 1 1 0 1 1 1

1 0 0 0 1 2 0 1 0 1 0 0 0 1

1 0 0 1 0 2 1 1 1 0 1 0 0 1

1 0 0 1 1 3 0 1 0 1 0 1 0 1

1 1 0 0 0 2 1 1 0 1 0 0 0 1

1 1 0 0 1 3 0 1 1 1 1 1 1

1 1 0 1 0 3 1 1 0 1 0 1 0 1

1 1 0 1 1 4 0 1 1 1 0 0

1 0 1 0 0 2 1 1 1 0 0 0 0 1

1 0 1 0 1 3 0 1 0 1 1 1 0 1

1 0 1 1 0 3 1 1 1 0 0 1 0 1

1 0 1 1 1 4 0 1 0 1 1 0 1 0

1 1 1 0 0 3 1 1 0 1 1 1 0 1

1 1 1 0 1 4 0 0 1 1 0 0 0 0

1 1 1 1 0 4 2< 1 1 0 1 1 0 1 0

1 1 1 1 1 5 0 0 1 1 0 1 0 0

Х1Х2Х3Х4 Х5Х6Х7Х8 Xn-lXn

Рис. 2.5: Схема, вычисляющая бинарное представление суммы новым способом.

2.2 Верхняя оценка на ALLMOD

Классическим примером симметрической функции является функция MOD, проверяющая, верно ли, что сумма входных битов имеет заданный остаток по заданному модулю:

MOD™ r(a;i,..., хп) = l<^>xi + ... + xn = r (mod т).

Известные оценки на схемную сложность таких функций:

• CB3(MOD2) =п-1.

• Св2(MOD?) = 2.5n - 0(1) [24].

• СВ2{М0Щ)>2>П + 0{1) [32].

• Св2{МСВД > 2.5п - 0(1) для т > 2 [24].

Как было показано в предыдущем разделе, произвольную симметрическую функцию можно вычислить с помощью схемы линейного размера. Из мощностных соображений следует, что для вычисления почти любых п симметрических функций понадобятся схемы размера 0(n2/logn). Известно, что для вычисления функций ТН" и ЕХ™ для всех % = 1,..., п достаточно линейных схем. Естественно задать тот же вопрос для MOD-функций. Ниже мы покажем, что и для вычисления всех MOD-функций достаточно схем почти линейного размера.

Пусть

ALLMOD" = {MOD;:t};;=1,

Теорема 2.

1. Размер минимальной схемы, вычисляющей ALLMOD", линеен.

2. Существует такая константа с, что размер минимальной схемы, вычисляющей ALLMOD"b Гп, не превосходит сп log log п.

Для доказательства мы снова воспользуемся методом предкоди-рования. В предыдущей главе мы уже использовали бинарный способ кодирования. Рассмотрим теперь его естественное обобщение для остатков.

Определим следующие два способа (бинарный и унарный) кодирования остатка г по модулю т:

log то

bin(r, т) = (bo, &1, — , ¿logто)> где г = ^ 2% (mod т)

i=0

ех(г, т) = (е0, еь ..., em_i), где а = 1 г ее г (mod m). Тогда

err^ + ... + т) = (MODJm, MOD"m,..., MODJU, J-

Будем опускать т, если т > п + 1. Тогда Ып(х\ + ... + хп) и ех(х\ + ... + хп) дают бинарное и унарное представление суммы входных битов. Ниже через т будем обозначать произвольное число, не превосходящее гг, а через q — степень простого, не превосходящую п. Положим также X = х\ + ... + хп.

Для доказательства Теоремы 2 нам понадобятся и эти, и другие способы предкодирования. Мы построим схему, состоящую из несколько блоков. На их основе вычислим интересующие нас MOD функции. Эти блоки представлены на рисунке 2.6.

Условно эти блоки можно поделить на три слоя. Верхний слой (Б1, Б2) вычисляет вспомогательные значения, на основе которых можно вычислить произвольную симметрическую функцию. Средний слой (БЗ-Б5) вычисляет некоторые бинарные, унарные представления и функции MOD, на основе которых в нижнем слое (Б6-Б8) вычисляются функции, являющиеся элементами ALLMOD™, Гп

Рис. 2.6: Схема, вычисляющая ALLMOD™ Гп и ALLMOD™.

и ALLMOD". При этом все эти блоки, кроме Б7, вычисляются схемами линейного размера.

В разделе 2.1 мы уже рассказали, как построить блок Б1 с помощью схемы линейного размера. Теперь на основе бинарного представления построим унарное (блок Б2).

Лемма 2.2.1. Существует схема размера 0(т), вычисляющая унарное представление ех(х\ + ... + хп,т) на основе бинарного Ып(х 1 + ... + хп,т).

Список литературы диссертационного исследования кандидат наук Деменков, Евгений Александрович, 2013 год

Литература

[1] Shannon Claude E. The synthesis of two-terminal switching circuits // BSTJ. 1949. T. 28, № 1. C. 459-466.

[2] Muller David E. Complexity in electronic switching circuits // Electronic Computers, IRE Transactions on. 1956. № 1. C. 1519.

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

[4] Blum Norbert. A Boolean function requiring 3n network size // Theoretical Computer Science. 1983. T. 28, № 3. C. 337-345.

[5] Wegener Ingo. The Complexity of Boolean Functions. Wiley-Teubner, 1987.

[6] Jukna Stasys. Boolean function complexity: advances and frontiers. Springerverlag Berlin Heidelberg, 2012. T. 27.

[7] Андреев А. Е. Об одном методе получения нижних оценок сложности индивидуальных монотонных функций // ДАН СССР. 1985. Т. 282, № 5. С. 1033-1037.

[8] Разборов А. А. Нижние оценки монотонной сложности некоторых булевых функций // ДАН СССР. 1985. Т. 281, № 4. С. 798801.

[9] Riordan John, Shannon Claude E. The number of two-terminal series-parallel networks //J. Math. Phys. 1942. T. 21, № 2. C. 8393.

[10] Храпченко В. M. О соотношении между сложностью и глубиной формул // Методы дискретного анализа в синтезе управляющих систем. 1978. № 32. С. 76-94.

[11] Hastad Johan. The shrinkage exponent of de Morgan formulas is 2 // SIAM Journal on Computing. 1998. T. 27, № 1. C. 48-64.

[12] Субботовская Б. А. О реализации линейных функций формулами в базисе // ДАН СССР. 1961. Т. 136, № 3. С. 553555.

[13] Храпченко В. М. Об одном методе получения нижних оценок сложности П-схем // Математические заметки. 1971. Т. 10, К21. С. 83-92.

[14] Impagliazzo Russell, Nisan Noam. The effect of random restrictions on formula size // Random Structures к Algorithms. 1993. T. 4, № 2. C. 121-133.

[15] Paterson Michael, Zwick Uri. Shallow circuits and concise formulae for multiple addition and multiplication // computational complexity. 1993. Т. 3, № 3. C. 262-291.

[16] Нечипорук Э. И. Об одной булевской функции // ДАН СССР. 1966. Т. 169, № 4. С. 765-766.

[17] Луиаиов О. Б. О реализации функции алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе {У, ->} // Сб. Проблемы кибернетики. 1961. № 6. С. 5-14.

[18] Лупанов О. Б. О реализации функции алгебры логики формулами из конечных классов (схемами ограниченной глубины) в базисе {V, ->} // Коллекция работ в математической кибернетики. 1977. Т. 2. С. 3-8.

[19] Hastad Johan, Jukna Stasys, Pudlak Pavel. Top-down lower bounds for depth-three circuits // Computational Complexity. 1995. T. 5, № 2. C. 99-112.

[20] Lamagna E .A., Savage J. E. On the logical complexity of symmetric switching functions in monotone and complete bases // Discrete

Optimization, Technical report, Brown University, Rhode Island. 1973.

[21] Клосс Б. M., Малышев В. А. Оценки на сложность для некоторых классов функций // Вестник Московского Университета. 1965. Т. Математика, № 4. С. 44-51.

[22] Schnorr Claus-Peter. Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen // Computing. 1974. T. 13. C. 155-171.

[23] Paul Wolfgang J. A 2.5n-lower bound on the combinational complexity of Boolean functions // SIAM Journal on Computing. 1977. T. 6, № 3. C. 427-443.

[24] Stockmeyer Larry J. On the combinational complexity of certain symmetric Boolean functions // Mathematical Systems Theory. 1976. T. 10, № 1. C. 323-336.

[25] Zwick Uri. A 4n lower bound on the combinational complexity of certain symmetric boolean functions over the basis of unate dyadic Boolean functions // SIAM Journal on Computing. 1991. T. 20, № 3. C. 499-505.

[26] Lachish Oded, Raz Ran. Explicit lower bound of 4.5n - o(n) for boolena circuits // Proceedings of the thirty-third annual ACM symposium on Theory of computing / ACM. 2001. C. 399-408.

[27] Iwama Kazuo, Morizumi Hiroki. An explicit lower bound of 5n -o(n) for boolean circuits // Mathematical foundations of computer science 2002. Springer, 2002. C. 353-364.

[28] Kulikov Alexander S., Melanich Olga, Mihajlin Ivan. A 5n- o(n) Lower Bound on the Circuit Size over Z72 of a Linear Boolean Function // Proceedings of Computability in Europe (CiE 2012). T. 7922. Springer, 2012. C. 432-439.

[29] Редькин H. П. О минимальной реализации двоичного сумматора // Проблемы кибернетики. 1981. Т. 38. С. 181-216.

[30] Hiltgen Alain PL. Cryptographically relevant contributions to combinational complexity theory. Hartung-Gorre Verlag, 1994. T. 3.

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

[32] New upper bounds on the Boolean circuit complexity of symmetric functions / Evgeny Demenkov, Arist. Kojevnikov, Alexander. S. Kulikov [и др.] // Information Processing Letters. 2010. T. 110, № 7. C. 264-267.

[33] Computing All MOD-Functions Simultaneously / Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin [и др.] //

Computer Science-Theory and Applications. Springer, 2012. C. 81-88.

[34] Ben-Sasson Eli, Kopparty Swastik. Affine dispersers from subspace polynomials // Proceedings of the Annual Symposium on Theory of Computing (STOC). T. 679. ACM Press, 2009. C. 65-74. URL: http://portal.acm.org/citation.cfm?doid=^1536414.1536426.

[35] Demenkov Evgeny, Kulikov Alexander S. An elementary proof of a 3n — o(n) lower bound on the circuit complexity of affine dispersers // Mathematical Foundations of Computer Science 2011. Springer, 2011. C. 256-265.

[36] Demenkov Evgeny. A Lower Bound on Circuit Complexity of Vector Function in U2 // 7th International Computer Science Symposium in Russia (CSR 2012) / под ред. Edward Hirsch, Juhani Karhumaki, Arto Lepisto [и др.]. Т. 7353 из Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2012. C. 81-88.

[37] Shannon Claude E. A symbolic analysis of relay and switching circuits // Electrical Engineering. 1938. T. 57, № 12. C. 713-723.

[38] Яблонский С. В. Реализация линейной функции в классе П-схем // Докл. АН СССР. Т. 94. 1954. С. 805-806.

[39] Schnorr Claus-Peter. The combinational complexity of

equivalence // Theoretical computer science. 1976. Т. 1, № 4. C. 289-295.

[40] Кричевский P. E. О сложности параллельно-последовательных схем, реализующих одну последовательность булевых функций // Проблемы кибернетики. 1964. № 12. С. 45-55.

[41] Ложкин С. А. О минимальных 7г-схемах для монотонных симметрических функций с порогом 2 // Дискретная математика. 2005. Т. 17, № 4. С. 108-110.

[42] Paterson Michael S., Pippenger Nicholas, Zwick Uri. Optimal carry save networks. Citeseer, 1990.

[43] Pudlak Pavel. A lower bound on complexity of branching programs // Mathematical Foundations of Computer Science 1984. Springer, 1984. C. 480-489.

[44] Fischer Michael J., Meyer Albert R., Paterson Michael S. fi(n\logn) Lower Bounds on Length of Boolean Formulas // SI AM Journal on Computing. 1982. T. 11, № 3. C. 416-427.

[45] Bach E., Shallit J. Algorithmic Number Theory // MIT Press. 1996. T. 679. c. 680.

[46] Savicky Petr, Zak Stanislav. A large lower bound for 1-branching programs: Tech. Rep.: TR96-036: ECCC, 1996.