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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

005538316

Деменков Евгений Александрович

ВЕРХНИЕ И НИЖНИЕ ОЦЕНКИ НА СХЕМНУЮ СЛОЖНОСТЬ ЯВНО ЗАДАННЫХ БУЛЕВЫХ ФУНКЦИЙ

01.01.06 — Математическая логика, алгебра и теория чисел

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

Санкт-Петербург — 2013

005538316

Работа выполнена на кафедре математических и информационных технологий Санкт-Петербургского академического университета — Научно-образовательного центра нанотехнологий РАН

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

Куликов Александр Сергеевич

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

завкафедрой, вед.н.с. отдела алгебры и математической логики НИИММ им. Н.Г.Чеботарева КГУ Аблаев Фарид Мансурович (Казанский федеральный университет)

кандидат физико-математических наук, научный сотрудник Подольский Владимир Владимирович (Математический институт им. В.А. Стеклова Российской академии наук) Ведущая организация: Уральский федеральный университет имени

первого Президента России Б.Н. Ельцина

Защита состоится "04" декабря 2013 г. в 16 часов на заседании диссертационного совета Д212.232.29 при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, В.0.10 линия 33-35, ауд. 74.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан "2 " Цо Я •б5Я 2013 г.

Ученый секретарь диссертационного совета

Нежинский В. М.

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

Актуальность темы.

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

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

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

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

переменных. Поскольку любую булеву функцию можно вычислить с помощью конъюнктивной нормальный формулы, то С{п) можно оценить сверху через 0(п2"). Шеннон в 1949 году показал, что для любого е и достаточно большого п верно неравенство С(п) > (1 — е)2"/п. В 1956 году Миллер доказал для любого конечного базиса верхнюю оценку С(п) = 0(2п/п). В 1959 году Лупанов показал, что С(п) < (1 + ап)2п/п, где а„ = 0(logп/п). Таким образом, мы знаем, что большинство функций от п переменных имеют схемную сложность Г2(2"/п).

Тем не менее, задача построения явно заданной булевой функции высокой схемной сложности оказалась очень трудной. Булеву функции} принято называть явно заданной, если прообраз единицы этой функции лежит в классе №. Более формально, в данной работе под булевой функцией / мы понимаем бесконечное семейство функций {/г: г € К}, где /,•: {0,1}® —> {0,1}. Такая функция называется явно заданной, если и;ен/~1(1) € NP.

Только в 1965 году Клосс и Малышев доказали первую нетривиальную нижнюю оценку 2п — 0(1). Рекордная же нижняя оценка в полном базисе 3п — о(п) доказана Блюмом в 1984. Она довольно нетривиальна и требует разбора большого количества случаев.

Помимо полного бинарного базиса часто рассматриваю базис из бинарных функций, которые можно вычислить с помощью одной дизъюнкции и нескольких отрицаний. Первый нетривиальный результат в этом базисе 3(п — 1) получен Шпором в 1974 году. Он доказал, что функция чётности имеет сложность 3(п— 1). Рекордный же результат 5п — о(п) получили 2002 году Ивама и Морицуми. В 2012 году Куликов, Меланич и Михайлин получили значительно более простое доказательство такой же оценки для одновременного вычисления нескольких линейных функций. Цели работы.

1. Усилить верхнюю оценку 5п + о(п) Лупанова на схемную сложность (над базисом В2) всех симметрических функций.

2. Получить нетривиальные верхние оценки на схемную сложность од-

новременного вычисления всех МОБ-функций.

3. Упростить доказательство нижней оценки 3п—о(п) на схемную сложность явно заданной функции (аффинного дисперсера).

4. Усилить нижнюю оценку на схемную сложность функции с п выходами.

Общая методика работы. В работе используются как стандартные методы доказательства новых оценок, так и новые идеи и подходы. Так, для улучшения верхних оценок используется стандартный метод предкодирова-ния. Для симметрических функций используется нестандартная кодировка суммы входных битов для построения более эффективного двойного сумматора. Для вычисления всех МОБ-функций одновременно используется метод предподсчётаст остатков по простым модулям.

Для доказательства нижней оценки используется стандартный метод элиминации элементов, однако в нём впервые используются произвольные линейные подстановки. Для доказательства нижней оценки для функции с п выходами усиливается метод Ламаньи и Сэведжа. Основные результаты.

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

2. Построена схема почти линейного размера, одновременно вычисляющая все МОБ-функции.

3. Получена новая рекордная нижняя оценка 7тг—о(п) на схемную сложность в базисе и2 функции из Вщп.

4. Получено более простое доказательство рекордной нижней оценки Зп - о(п) на схемную сложность явной заданной булевой функции в базисе В2-

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

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

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

Апробация работы. Основные результаты обсуждались на следующих конференциях: международный симпозиум 36th International Symposium On Mathematical Foundations Of Computer Science (MFCS 2011), Польша, 2011; международный симпозиум 7th International Computer Science Symposium in Russia (CSR 2012), Россия, 2012. Результаты, лежащие в основе диссертации, также были доложены на семинаре в Московском государственном университете. Публикация в трудах конференции 7th International Computer Science Symposium in Russia получила приз как лучшая студенческая работа.

Публикации. Основные результаты диссертации опубликованы в четырёх работах [1], [2], [3], [4].

Работа [1] написана самостоятельно диссертантом. В работе [4] диссертантом доказана верхняя оценка 4.5п на схемную сложность вычисления суммы входных битов, изложенная в разделе 2. В работе [3] диссертанту принадлежит доказательство ключевой леммы 6, из которой выводится основной результат статьи. Теорема 1 доказана А. Куликовым и X. Мо-рицуми, теорема 2 доказана авторами работы совместно. В работе [2] диссертанту принадлежит идея использования переменных исходящей степени 1, с помощью которой доказывается теорема 1, содержащая основной результат статьи. А. Куликову принадлежит идея использования аффинного дисперсера и доказательство леммы 1. Работы [2], [3], [1] опубликованы в изданиях, входящих в список рекомендованных Высшей аттестационной

комиссией на момент публикации.

Структура и объем диссертации. Диссертация объёмом 60 страниц состоит из введения и трёх основных глав, разбитых на разделы и подразделы. Список цитируемой литературы состоит из 46 наименований.

Содержание работы

Основные определения. Перед изложением содержания работы приведём необходимые определения.

Через Вп<т обозначим множество всех булевых функций /: {0,1}" —> {0,1}т. В п, 1 обозначается через Вп, Функция / G Вп называется симметрической, если её значение зависит только от суммы входных битов. Другими словами, должен существовать вектор v € {0, l}n+1 (называемый вектором значений /) такой, что f(xi,...,x„) = v3, где s = Yj\<i<nxi-Фундаментальные симметрические функции EX, ТН и MOD определяются следующим образом:

ЕХ^Х!,...,^) = =

1 <i<n

THJ(ii,..., xn) = Xi>k,

1 <i<n

MOD^ r(xb...,a;„) = 1 о = r (mod m).

l<j<n

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

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

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

значений.

xi x2 хз 1

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

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

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

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

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

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

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

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

Следующим результатом второй главы является почти линейная верхняя оценка на схемную сложность одновременного вычисления всех MOD-функций. Несложно показать, что для почти всех наборов из п симметрических функций схемная сложность почти квадратична — 6(n2/logn). Ни одного такого явного набора, однако, неизвестно. В то

же время известно, что для одновременного вычисления всех функций ЕХ и ТН достаточно схем линейного размера. Мы усиливаем данный результат, доказывая, что и все MOD-функции можно вычислить схемами почти линейного, а для некоторых случаев линейного размера.

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

Заключительным результатом диссертации является нижняя оценка 7п — о(п) на схемную сложность в базисе U2 функции из Bn¡n. Это улучшает предыдущую известную оценку 6п — о(п), получающуюся применением метода Ламаньи и Сэвэджа к оценке 5п — о(п), доказанной Ивамой и Мо-рицуми. В отличие от метода элиминации элементов, использующемся в доказательстве предыдущей оценки, здесь анализируется часть схемы у выходов, а не входов.

Публикации автора по теме диссертации

[1] 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 [и др.]. T. 7353 из Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2012. С. 81-88.

[2] 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.

[3] Computing All MOD-Functions Simultaneously / Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin [n flp.] // Computer Science-Theory and Applications. Springer, 2012. C. 81-88.

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

Подписано в печать 29.10.2013г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 3325.

Отпечатано в ООО «Издательство "ЛЕМА"» 199004, Россия, Санкт-Петербург, В.О., Средний пр., д. 24 тел.: 323-30-50, тел./факс: 323-67-74 e-mail: izd_lema@mail.ru http://www.lemaprint.ru

04201452 4 85

САНКТ-ПЕТЕРБУРГСКИЙ АКАДЕМИЧЕСКИЙ УНИВЕРСИТЕТ -НАУЧНО-ОБРАЗОВАТЕЛЬНЫЙ ЦЕНТР НАНОТЕХНОЛОГИЙ РАН

На правах рукописи

Деменков Евгений Александрович

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

01.01.06 — Математическая логика, алгебра и теория чисел

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: к.ф.-м.н. А. С. Куликов

Санкт-Петербург 2013

Оглавление

Введение 4

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

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

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

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

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

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

1.3 Результаты..................................................17

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

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

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

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

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

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

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

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

Литература 54

Введение

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

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

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

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

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

Изучение булевых схем можно найти ещё в работах Шеннона [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-функции можно вычислить схемами почти линейного размера. Результат представлен на международной конфе�