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

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

Забалуев Руслан Николаевич

О СРЕДНЕЙ СЛОЖНОСТИ БУЛЕВЫХ ФУНКЦИЙ

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

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

МОСКВА - 2004

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

Научныйруководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук профессор А. В. Чашкин. доктор физико-математических наук профессор Л. А. Шоломов; кандидат физико-математических наук В. В. Кочергин. Московский государственный педагогический университет.

Защита диссертации состоится 18 февраля 2005г. в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М.В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М. В. Ломоносова (Главное здание, аудитория 14-08).

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

Автореферат разослан 18 января 2005г.

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

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

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

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

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

1Чашкин А. В. О среднем времени вычисления значений булевых функций // Дискрет, анализ и исслед. операций. Вып. 1.1997. Т. 3. № 1. С. 60-78

2Чашкин А. В. Об одном методе вычисления частичных булевых функций // Математические вопросы кибернетики. Вып. 12, М.: Наука, 2004, С. 231-2.46.

:'ОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

СПстсИрг * л ' 03

образом Т(Р) = 2 n22ïe{oi}nTp(%) №»(i) - число команд, выполненных программой Р до ее остановки).

Асимптотика функции Шеннона схемной сложности для класса всех функций п переменных получена О. Б. Лупановым3: ДРг(я)) ~

Сложность реализации монотонных функций схемами из функциональных элементов изучалась специалистами по синтезу управляющих систем в течение многих лет. С. В. Яблонский4 показал, что Lß(M(n)) — фунция Шеннона для реализации схемами в базисе В класса монотонных функций от п переменных — есть малая величина по сравенению с Ь(Рг(п)). Конкретные верхние оценки величины Lß(M(n)) (хотя и существенно отличающиеся от нижней) получили В. И. Резник5 и Э. И. Нечипорук6. Далее В. К. Коробков7 нашел порядок функции Шеннона:

( " ) 8 Lß(M(nj) ~ ^ . Серию результатов продолжил Ж. Ансель8, улучшив

константу в верхней оценке В. К. Коробкова. Затем А. Б. Угольников9

установил асимптотику функции Шеннона: Lß(M(n)) ~ где

р(В) — приведенный вес базиса В. Аналог послегшей гЬопмуггы был получен Н. Пиппенджером10:Хв(М(п)) -p(fl)Ila0l2 ~ В У11™«1-нутых выше оценках для функции предполагалось, что базис В полный.

Помимо задач реализации монотонных функций в полных базисах также рассматривались задачи реализации этих функций в неполных базисах. Н. П. Редькиным11 был найден порядок величины Lß(M(n)), где В

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

4Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // УМН. 1957. 12. Вып. 6. С. 189-196

5 Резник В. И. О реализации монотонных функций схемами из функциональных элементов // ДАН СССР. 1961. 139. № 3. С. 566-569

6Нечипорук Э. И. О вентильных схемах // Международный симпозиум по теории релейных схем и конечных автоматов. Тез. док. М. 1962. С. 42-43

7Коробков В. К. О монотонных функциях алгебры логики // Проблемы кибернетики. Вып. 13. М.: Наука, 1965. С. 5-28

8Hansel G. Sur le nombre des fonctions booleannes monotones de n variables // C. R. Acad. Sci. Paris. 1966. 262. P. 1088-1099

'Угольников А. Б. О реализации монотонных функций схемами из функциональных элементов // Проблемы кибернетики. Вып. 31. М.: Наука, 1976. С. 167-185

10Pippendger N. The Complexity of monotone-boolean functions // Math. Systems Theory. 1978. № 11. P. 289-316

11Редькин Н.П. О реализации монотонных булевых функций контактными схемами // 4-я Всесоюзная конференция по проблемам теоретической кибернетики: Тез. докл. - Новосибирск, 1977. С. 180-181; Редькин Н. П. О реализации монотонных булевых функций схемами из функциональных элементов // Проблемы кибернетики. Вып. 35. М.: Наука, 1979. С. 87-110

— собственный базис класса.Л/(га). А. Е. Андреев12 получил асимптотику функции Ьв(М(п)) для собственных базисов класса М(п), записанную в том же виде, что и у Н. Пиппенджера.

Инвариантные классы булевых функций были введены С. В. Яблонским13 с целью нахождения подмножеств булевых функций, имеющих более простую реализацию контактными схемами, чем почти все функции. Им было показано, что сложность реализации контактными схемами функции / от п переменных из произвольного ненулевого инвариантного класса не превосходит величины <7^(1 4- о(1)) при п —* оо. Эту же оценку для схемной сложности функции / получил О. Б. Лупанов14.

Для класса S симметрических функций известно15, что ¿(5) х п.

А. В. Чашкин рассматривал различные вопросы, касающиеся средней сложности булевых функций при их реализации неветвящимися программами с условной остановкой. Им было показано16, что средняя сложность произвольной симметрической функции / зависит от максимального числа последовательных слоев /¿(/), на которых эта функция принимает одинаковые значения: Т(/) X п — + 2. Для каждой булевой функции / € -РгСя) установлено17, что верхняя оценка ее средней сложности асимптотически не превосходит величины а для почти каждой функции / £ Рг(^) — нижняя оценка18 средней сложности асимтотически не меньше чем

4 п

Последняя оценка найдена применением "мощностного" метода18 получения нижних оценок средней сложности. В отличие от "мощностного"

14

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

Для многих классов вопрос нахождения как порядка, так и асимп-

12Андреев А. Б. Синтез схем из функциональных элементов в полных монотонных базисах // Мат. вопросы кибернетики. Вып. 1. М.: Наука, 1985. С. 114-139

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

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

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

16Чашкин А. В. Средняя сложность симметрических булевых функций // Вестник МГУ. Сер. 1. Математика. Механика. 2003. № 1. С. 16-19.

17Средняя сложность булевых функций // Дискретная математика и ее приложения, М.: Изд-во Центра прикладных исследований при механико-математическом факультете МГУ. 2001. С. 145-170

18Чашкин А. В. О сложности сужений булевых функций // Дис. д-ра, физ.-мат. наук, МГУ им. М. В. Ломоносова, мех.-мат. фак., М. 1999

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

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

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

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

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

2. Для каждой монотонной функции получена верхняя оценка средней сложности, причем она меньше по порядку чем асимптотика функции Шеннона для реализации схемами класса таких функций и оптимальна по порядку для почти всех таких функций.

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

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

Приложения. Работа носит теоретический характер. Ее результаты могут быть полезны специалистам Московского государственного университета им. М. В. Ломоносова, Института прикладной математики им. М. В. Келдыша РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. М. В. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственного университета.

Апробация работы. Результаты диссертации докладывались на семинарах механико-математического факультета МГУ под руководством академика РАН О. Б. Лупанова «Математические вопросы кибернетики» (2004) и «Синтез управляющих систем» (2004), на XIV Международной школе-семинаре «Синтез и сложность управляющих систем» в Нижнем Новгороде (2003), на УШ Международном семинаре «Дискретная математика и ее приложения» в Москве (2004), на XV Международной школе-семинаре «Синтез и сложность управляющих систем» в Новосибирске (2004).

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

Структура работы. Диссертация состоит из введения, четырех глав и списка литературы, содержащего 25 наименований. Общий объем диссертации — 74 страницы.

Обзор содержания диссертации

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

,Л[п]). Функции, входящие в вычислительные команды неветвящихся программ, берутся из базиса всех не более чем двуместных функций.

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

Раздел 1.1 посвящен изучению схемной сложности полиномов степени к = 2,...,п в естественном б а{©?&,и} (& =е 1 — тривиальный случай). Каждый полином степени к задается суммой по модулю 2

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

Теорема 3. Пусть f(xi,...,xn) € Я^п], где 2 < к < п - logn—

4 log log п. Тогда при п—*оо справедливо соотношение

Нижняя оценка схемной сложности почти каждой функции из класса P^ln] следует из "мощностного" метода получения нижних оценок14 и асимптотически равна величине, упомянутой в предыдущей теореме.

Теорема 3 является следствием теорем 1 (случай log п < к < п — logn - 41oglogn) и 2 (2 < к < logn) из раздела 1.1.2. Теорема 1 доказывается с использованием верхней оценки19 для сложности реализации схемами вспомогательной системы а, состоящей из М линейных однородных функций, каждая из которых зависит не более чем от N переменных:

Лемма 1. Если N = 20<м>, М = 2°W и NM оо, тогда выполнено асимптотическое неравенство

L(a)<

NM

r(l + o(l)).

\ogiNMy

Доказательство теоремы 2 проведено, опираясь на конструкции схем,

аналогичные конструкциям О. Б. Лупанова3.

Применяя теорему 3 и "мощностной" метод для схемной сложности, в разделе 1.1.3 установлена сложность реализации полиномов в нетривиальном случае:

Теорема 4. Пусть 2 <к<п. Тогда для каждого полинома / € Р^Щ при п—> оо справедливо соотношение

19Pippendger N. On the evalution of powers and monomials. SIAM J. Comput. Vol 9, № 2, May 1980. P. 230-250.

и для почти всех / € [п] выполняется неравенство

Раздел 1.2 посвящен нижним оценкам средней сложности полиномов. Основным результатом этого раздела является

Теорема 5. Для почти каждого полинома / € Р2*[п], где 2 <к<п, при П —» 00 выполнено неравенство

Этот результат получен, опираясь на "мощностной" метод А. В. Чаш-кина для получения нижних оценок средней сложности и свойства однозначного задания полиномов степени к по некоторым его значениям.

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

Теорема 6. Для каждого полинома / Е -^[я], где 2 < к < п, при п со выполнено неравенство

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

в два раза:

Теорема 7. Для каждого полинома / € Р*И» Гп/21 _ й\/п <

к <п иа> 0, при п—юо выполнено неравенство

Глава 2 посвящена средней сложности монотонных функций. Для почти каждой монотонной функции f(xi,...,a;n), учитывая строение таких функций, описанное в работе А. Д. Коршунова20, легко установить следующую верхнюю оценку средней сложности:

Основным результатом главы 2 является теорема из раздела 2.3, утверждающая справедливость оценки (1) для каждой монотонной функции f(x h...,xn):

Теорема 8. Для каждой функции f G М(п) при п —* оо выполнено соотношение п

где а — некоторая положительная константа.

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

Лемма 8. Пусть f(xi,...,xn) — монотонная функция. Тогда существуют такие числа р, q, г, что количество наборов, на которых функции /у1**

и fpq® не совпадают, не превосходит величины

где — функция п — 3 переменных, получающаяся из функции f подстановкой двоичных значений S, 'у, г) вместо переменных хр, хч и хг

20 Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. Вып. 38. М.: Наука. 1965. С. 5 - 108

соответственно.

Эта лемма представляет собой модификацию одного утверждения из метода А. В. Чашкина21. Ее доказательство рассмотрено в разделе 2.1.

В разделе 2.4 установлены нижние оценки средней сложности монотонных функций, используя "мощностной" метод А. В. Чашкина:

Теорема 9. Для почти каждой функции / € М(п) при п —* оо

выполнено соотношение

где Ь — некоторая положительная константа.

В главе 3 рассматривается средняя сложность функций из инвариантных классов. О средней сложности функций п переменных из некоторых инариантных классов, а именно: Рг (класс всех функций), М (класс монотонных функций), S (класс симметрических функий), — было упоя-нуто выше. В разделе 3.1 доказывается следующее утверждение о средней сложности функций п переменных из произвольного ненулевого инвариантного класса

Теорема 10. Пусть п-* оо. Тогда (г) для каждой функции /(х1,..,,хп) € (¡¡а выполнено

(И) для почти каждой функции $(х\,...,хп) € ф справедливонеравен-

Поэтому для почти каждой функции / € £?„, где а ф 0, верно соотношение: Т(/) ж Ь{/).

В разделе 3.2 приведены примеры нулевых инвариантных классов, где выполняется предыдущее соотношение. Также рассмотрены некоторые нулевые инвариантные классы, где для почти каждой функции / от п переменных выполнено Т(/) = о(Ц/)).

21 Чашкин А. В. Об одном методе вычисления монотонных функций // Ломоносовские чтения. Секция: Математика, механика. 2004

В главе 4 предложена модель вычисления функций неветвящимися программами с условной остановкой, допускающими только однократное использование промежуточных значений. Такие программы сокращенно названы О-программами. Они отличаются от неветвящихся программ, рассматриваемых ранее, тем, что выход каждой вычислительной команды может использоваться только один раз. Понятие средней 0-сложности Т0(/} для булевой функции / при вычислении О-программами определяется также, как и обычная средняя сложность Т(/).

В разделе 4.1 оценивается сверху число ЛТ0(Ь,п) различных О-про-грамм длины L, вычисляющих функции от п переменных:

Лемма 12. Для любого положительного целого числа I справедливо соотношение

где с\ ис2 — некоторые положительные константы.

С использованием этой леммы (для пункта (г)) в разделе 4.2 доказывается утверждение о средней О-сложности:

Теорема 12. Пусть п —* оо. Тогда: (г) для почти каждой функции f € Рг(га) выполнено соотношение

(«) для каждой функции f £ Рг(п) верно неравенство

Таким образом, установлена асимпототика функции Шеннона Т0(п) для средней О-сложности функций п переменных: Т0(п) ~ Благодарности

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

Работы автора по теме диссертации

1. Забалуев Р. Н. О сложности реализации полиномов Жегалкина // Дискретная математика. Том 16. Вып. 1. 2004. С. 79 - 94.

2. Забалуев Р. Н. О средней сложности булевых функций, заданных полиномами Жегалкина // Дискретный анализ и исследование операций. Серия 1. 2004. Т. И. № 3. С. 3 - 15.

3. Забалуев Р. Н. О средней сложности полиномов Жегалкина // Материалы XIV Международной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 27 октября - 1 ноября 2003 г.). Нижний Новгород: Издательство Нижегородского государственного педагогического университета, 2003. С. 38 -43.

4. Забалуев Р.Н. О средней сложности функций из инвариантных классов // Материалы VIII Международного семинара "Дискретная математика и ее приложения" (Москва, 2-6 февраля 2004 г.). М.: Издательство механико-математического факультета МГУ, 2004. С. 66 - 69.

5. Забалуев Р. Н. О средней сложности вычислений монотонных функций // Материалы XV Международной школы-семинара "Синтез и сложность управляющих систем" (Новосибирск, 18 октября - 23 октября 2004 г.). Новосибирск: Издательство Института математики СО РАН. 2004. С. 40-45.

Подписано Э печать (>1)

Формат 60x84/16. Усл.псч.л. /,С

Тираж ¡СО экз. Заказ „.*> Отпечатано в Отделе печати МГУ

- 968

Введение

Глава 1 О средней сложности полиномов Жегалкина.

1.1 Схемная сложность полиномов Жегалкина.

1.1.1 Прямоугольное представление полиномов.

1.1.2 Реализация однородных полиномов.

1.1.3 Реализация полиномов Жегалкина.

1.2 Нижние оценки средней сложности.

1.3 Верхние оценки средней сложности.

Глава 2 О средней сложности монотонных функций. 2.1 Вспомогательные утверждения о монотонных функциях

2.2 Об одном разбиении множества двоичных наборов.

2.3 Верхняя оценка.

2.4 Нижние оценки.

Глава 3 О средней сложности функций из инвариантных классов

3.1 Ненулевые инвариантные классы.

3.2 Нулевые инвариантные классы.

Глава 4 О реализации функций О-программами.

4.1 Оценка числа О-программ.

4.2 Оценки средней О-сложности.

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

Рассматриваемые программы были введены А. В. Чашкиным [13]. Они обобщают понятие схемы из функциональных элементов и являются естественной моделью неветвящихся вычислений, т. е. вычислений в которых нет условного перехода и косвенной адресации, но есть возможность досрочного прекращения работы при выполнении определенного условия. Такие вычисления можно представить следующим образом. Вычисления выполняет процессор, снабженный памятью, состоящей из отдельных ячеек. Эти ячейки будем обозначать символами у{. В памяти выделяется особая ячейка, содержимое которой объявляется результатом работы программы. Эта ячейка обозначается символом 2;. Процессор работает под управлением программы, являющейся последовательностью вычислительных команд и команд остановки. Каждая вычислительная команда за единицу времени вычисляет значение некоторой двуместной булевой функции, аргументами которой являются величины, содержащиеся в определенных ячейках памяти. Вычисленный результат также помещается в одну из ячеек памяти. Команда остановки может прекратить выполнение программы. Каждая такая команда имеет единственный аргумент - содержимое некоторой ячейки памяти. Если значение аргумента равно единице, то процессор прекращает работу. Если значение аргумента равно нулю, то выполняется следующая команда программы. Естественной мерой сложности таких программ является среднее по всем возможным аргументам время работы (средняя сложность).

В многочисленных работах А. В. Чашкина были исследованы различные Ф вопросы, связанные со средней сложностью. В частности, исследованы: средняя сложность конкретных функций и "почти"всех функций [13, 14, 15], средняя сложность частичных функций и частичных функций данного веса [16], средняя сложность симметрических функций [17].

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

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

Пусть Р2(2) — множество всех не более чем двуместных булевых функций, X = {rci,. ,хп] — множество независимых булевых переменных. Введем множество У = {yi,. ,уп} и переменную z. Переменные из множества Y назовем внутренними, а переменную z — выходной переменной. Пусть, далее, а е Y U {z}, b, с € X U У U {z}, f G ^2(2). Вычислительной командой р назовем выражение переменную а назовем выходом этой команды, а величины Ь, с — ее входами. Если переменная а является выходом команды р, то будем говорить, что команда р изменяет значение этой переменной, а если а не является выходом р, то будем говорить, что команда р не изменяет ее значение. Командой остановки р назовем выражение р: а = /(6, с),

1) р : Stop(b) а переменную Ь назовем входом этой команды.

Последовательность Р = р\. .pi. .рь, состоящая из вычислительных команд и команд остановки, называется неветвящейся программой с условной остановкой, допускающей многократное использование промежуточных значений (сокращенно М-программой), если при любом j {1,2,., L} каждый вход команды pj есть либо независимая переменная, либо выход некоторой вычислительной команды pi, где г < j.

Неветвящаяся программа работает в дискретные моменты времени t = 0,1, 2,., не изменяет значения независимых переменных и изменяет значения внутренних и выходных переменных. Значения yi{x\t) внутренних переменных yi и значение z(x;t) выходной переменной z программы Р в произвольный момент времени t на наборе независимых переменных х = (rci,., хп) определим индуктивно:

• в начальный момент времени, t = 0, значения всех внутренних и выходной переменных считаем неопределенными;

• если команда pt не изменяет значения внутренней переменной yi (выходной переменной z), то положим у{(х\ t) = Уг(х; t - 1), z(x\ t) = z(x\ t - 1);

• если команда pt изменяет значение внутренней переменной yi (или выходной переменной z), и значения входов команды pt в момент времени t — 1 равны соответственно Ь{х; t — 1) и с{х\ t — 1), то положим

Уг{х) t) = ft(b(x] t-1), с{х; t- 1)), z(x-t) = ft{b(x;t-l),c{x;t-l)).

Значением команды pt на наборе независимых переменных х = (a;i,., хп) назовем значение ее выхода в момент времени £ и обозначим через pt{x).

Пусть ptl,., Ptr — все команды оставновки программы Р, причем t\ < . < tr. Тогда j-ю команду остановки программы Р будем обозначать символом Sj, т. е. Sj = ptj. Вычислительную команду Pi (переменную х{) назовем нулевым аргументом команды остановки Sj = pj>, если: i) выход команды Pi (переменная х{) является входом команды Sj] (И) среди команд pt, г < t < f, нет команды выход которой совпадает с выходом р{.

Нулевой аргумент команды Sj обозначим через Sj. Вычислительную команду Pi назовем первым аргументом команды остановки Sj = pj> (обозначим его через sj), если: г) выход команды pi является выходной переменной г; (гг) среди команд pt, г < t < j', нет команды выходом которой является выходная переменная

Будем говорить, что к-я команда остановки Sk прекращает вычисления программы Р на наборе х, если

Результат действия программы Р на наборе х обозначим через Р(х) и определим следующим образом: т. е. Р{х) равно значению выходной переменной в момент остановки программы. Легко видеть, что

Сложностью L(P) программы Р назовем число команд этой программы. Временем работы Тр(х) программы Р на наборе переменных х назовем число команд, выполненных до остановки программы. Величину s^x) = ■. = sUix) = 0, sl(x) = 1. z{x; tk), если s?(£) = • • • = s\^x) = 0, = 1 z(x\ L), если s5(5) = • • • = s\(x) = 0,

P(x) = V • • • Vil(x)4(x). . ^(zjsjft®)^;**) V .

V s5(£)s5(£) • • • s^Or^Or^Oz; tr) V . s°r(x)z(x; L). где суммирование производится по всем двоичным наборам длины п, назовем средним временем работы программы Р. Если для некоторой булевой функции / и любого двоичного набора х справедливо равенство f(x) = Р(ж), то будем говорить, что программа Р вычисляет функцию /. Величину

T(/) = minT(P), где минимум берется по всем программам, вычисляющим /, назовем средней сложностью (средним временем вычисления) функции /. Программу Р, вычисляющую функцию /, для которой справедливо равенство Т(Р) = T(f), назовем минимальной программой.

Число элементов минимальной схемы из функциональных элементов, реализующей функцию / в базисе В назовем сложностью f в базисе В и обозначим символом LB(f). Если Q — некоторый класс функций, тогда величину LB(Q) — maxLB(f), где максимум берется по всем функциям / из Q, назовем сложностью класса Q или функцией Шеннона для реализации схемами в базисе В функций из класса Q. Через Рг(^) обозначим класс всех булевых функций п переменных. Пусть Q(n) — некоторый класс функций от п переменных. Будем говорить, что некоторое свойство выполнено для почти каждой функции из класса Q(n), если для подкласса V(n) функций, не обладающих этим свойством, справедливо lim = 0. n—>00

Полиномом Жегалкина называется сумма по модулю 2 коньюнкций (мономов), состоящих из независимых переменных; степень монома равна числу переменных, из которых он состоит; степень полинома определяется как максимальная из степеней входящих в него мономов. Полином называется однородным, если он либо равен тождественно нулю либо все его мономы состоят из одинакового числа переменных. Класс функций, заданных полиномами (однородными полиномами) Жегалкина, степень каждого из которых не превосходит к (в точности равна к), обозначим через РЦп] (-Р^'Л[п]).

Диссертация состоит из четырех глав. В главе 1 изучается схемная и средняя сложность булевых функций, заданных полиномами Жегалкина (далее просто полиномами). Раздел 1.1 посвящен изучению схемной сложности полиномов степени к = 2, .,п (при к = 1, очевидно, схемная сложность полиномов линейная). Каждый полином степени к задается суммой по модулю 2 однородных полиномов. Поэтому схемная сложность однородных полиномов представляет особый интерес. В разделе 1.1.1 вводится специальное представление полиномов, которое позволяет свести вычисления однородных полиномов к вычислению систем линейных функций. Далее в разделе 1.1.2 для каждого однородного полинома f(xi,.,xn) степени к (2 < к <п — log п — 4 log log п) доказывается верхняя оценка его схемной сложности: 1/{ф)&}(/) < (1 + о(1)), являющаяся асимптотически оптимальной для почти каждого рассматриваемого полинома, что следует из работы [6] (все логарифмы берутся по основанию 2). Опираясь на этот результат, в разделе 1.1.3 показывается, что сложность каждого полинома из класса Р§ [п]

2 < к < п) в базисе {0, &, 1} не превосходит величины log(g*fc)(l + °(1))> гДе к

Sn,k = ]С ) > которая также асимптотически оптимальна для почти каждого го такого полинома. Значит, этой же величиной оценивается сверху и средняя сложность Т(/) полинома / € Р^п] (2 < к < п). Для более половины значений к верхнюю оценку для T(f) удается понизить в два раза (см.

1 S

раздел (1.3)): Т(/) < | • iog(g*fc)(l + о(1)). В разделе 1.2 изучаются нижние оценки средней сложности полиномов степени к (2 < к < п). Для почти каждого полинома / £ РЦп] найдена нижняя оценка его средней сложности: пл > I • cifcU + 0(1)).

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

Пусть р{В) — приведенный вес базиса В.

В 1957 г. С. В. Яблонский [21] показал, что

LB(M(n)) = o(^j. (3)

Нижняя оценка для величины LB{M{n)), получаемая из "мощностных соображений", имеет вид [6]:

Ьв(М(п)) > + о(1)). ь

Конкретные верхние оценки (хотя и существенно отличающиеся от нижней) получили В. И. Резник [11] в 1961 г. и Э. И. Нечипорук [8] в 1962 г. В 1965 г. В. К. Коробков [2] установил, что

В сочетании с принципом локального кодирования О. Б. Jlyпанова [6] это позволило ему найти порядок функции Шеннона:

LB(M(n)) ж (4)

В 1966 г. Ж. Ансель, опираясь на свой метод перечисления монотонных функций [22] и принцип локального кодирования, несколько уменьшил константу в верхней оценке В. К. Коробкова. Д. Клейтман [23] в 1969 г. построил асимптотически оптимальное кодирование монотонных функций и показал, что п ) log \М(п)\ ~ ть

Используя перечислительную конструкцию Д. Клейтмана и принцип локального кодирования, в 1976 г. А. Б. Угольников [12] получил асимптотику функции Шеннона: п )

LB(M(n)) - (5)

Усиление последней формулы было получено Н. Пиппенджером [24] в 1978

LB(M(n)) - р(В)-^ х ЬШШ (6) п п п

Отметим также принадлежащий А. В. Чашкину метод доказательства соотношения (4) [18] (2004 г.), где вычисления монотонных функций несложным образом сводятся к вычислению частичных функций. При доказательстве формул (3) — (6) предполагалось, что базис В полный во множестве всех булевых функций Р2(п).

Помимо задач реализации монотонных функций в полных базисах также рассматривались задачи реализации этих функций в неполных базисах. Н. П. Редькиным [9, 10] была установлена справедливость формулы (4) для собственных базисов класса М(п) (1977 г.). В 1985 г. А. Е. Андреев [1] получил справедливость формулы (6) для собственных базисов класса М(п), усовершенствовав перечислительную процедуру Д. Клейтмана.

Для почти каждой монотонной функции f(xi, .,хп), учитывая строение таких функций, описанное в работе А. Д. Коршунова [3], легко установить следующую верхнюю оценку средней сложности: пп

T(/)<a-j(l + o(l)), а > 0. (7) ть

Основным результатом главы 2 является теорема 8, утверждающая справедливость оценки (7) для каждой монотонной функции f(xi,.,xn). В разделе 2.2 строится специальное разбиение множества всех двоичных наборов, зависящее от конкретной монотонной функции; при построении применяется лемма 8, рассмотренная в разделе 2.1, которая представляет собой модификацию одного утверждения из метода А. В. Чашкина [18]. Теорема 8 доказывается, существенно опираясь на упомянутое разбиение. Четвертый раздел главы 2 посвящен нижним оценкам средней сложности монотонных функций, где для почти каждой функции / G М(п) показана справедливость неравенства: on

T(f) > b-2(l + o(l)).

Средняя сложность функций из некоторых инвариантных классов [20] изучается в главе 3. Верхние и нижние оценки средней сложности функций п переменных из некоторых инариантных классов, а именно: Р2 - класс всех булевых функций, L - класс всех линейных функций, S - класс всех симметрических функций, - получены в работах А. В. Чашкина [13, 17, 14, 15]. В частности, им было показано, что средняя сложность каждой функции из Р2(п) не превосходит величины + [14], и средняя сложность почти каждой функции из Рг(^) не меньше чем | • ^-(1 + о(1)) [15]; для суммы по модулю 2 получено точное значение средней сложности [15]: T(x\®x2® .фхп) = п — 1; средняя сложность произвольной симметрической функции / зависит от максимального числа последовательных слоев //(/), на которых эта функция принимает одинаковые значения: Т(/) х п — fi(f) + 2 (см. [17]).

В разделе 3.1 показано, что для каждой функции f(x\,.,хп) из инвариантного класса Q с параметром а ^ 0 справедливо неравенство T(f) < |^(1 + о(1)); и для почти каждой функции f(x 1,., хп) G Q верно соотношение T(f) > ^^(1+о(1)). Поэтому, учитывая оценки схемной сложности для функций из ненулевых инвариантных классов [6], для почти каждой функции f(x 1, .,хп) из класса Q средняя сложность по порядку совпадает со схемной:

T(f) ^ L(f). (8)

Среди нулевых инвариантных классов ситуация несколько иная. Нетрудно привести классы, где для почти каждой функции f(x 1,., хп) выполнено

T(f) = o(L(f)). (9)

Например, таким свойством обладают Qv ~ класс всех дизъюнкций в объединении с нулем и единицей, Q& - класс всех коньюнкций в объединении с нулем и единицей, любой класс Qq , введенный в [20], а также класс Qi, рассмотренный в разеделе 3.2. Учитывая результаты раздела 2, свойством (9) обладает и класс всех монотонных функций - М. Но соотношение (9) выполнено не для всех нулевых инвариантных классов. Например, класс L удовлетворяет соотношению (8). Из разделов 1.1 и 1.2 следует, что соотношению 8 также удовлетворяет нулевой инвариантный класс, состоящий из полиномов Же-галкина, степень каждого из которых не превосходит к (к — фиксированое положительное целое число).

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

О-программы работают также как и М-программы. Понятие средней 0-сложности или среднего времени О-вычисления функции / (обозначается через Т0(/)) и минимальной О-программы определяется подобным образом что и для М-программ.

Как уже говорилось, в [14, 15] найдены верхняя, + о(1)), и нижняя, §^-(1 + о(1)), оценки среднего времени вычисления М-программами каждой и почти каждой функции п переменных соответственно, но асимптотически точное значение средней сложности хотя бы для почти каждой функции не известно. В главе 4 исследуется функция Шеннона Т0(п) для среднего времени вычисления О-программами функций из класса Р^ [тт.].

В разделе 4.1 получена оценка числа различных О-программ, вычисляющих функции п переменных при п —> оо. Используя эту лемму и применяя методы, развитые в [15], в разделе 4.2 доказывается следующая нижняя оценка средней О-сложности для почти каждой функции f(x 1,., хп):

В этом же разделе найдена верхняя оценка средней О-сложности для каждой функции f от п переменных:

Таким образом, получена асимптотика функции Шеннона Т0{п):

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

1. Андреев А. Е. Синтез схем из функциональных элементов в полных монотонных базисах // Мат. вопросы кибернетики. Вып. 1. М.: Наука, 1985. С. 114-139.

2. Коробков В. К. О монотонных функциях алгебры логики // Проблемы кибернетики. Вып. 13. М.: Наука, 1965. С. 5-28.

3. Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. Вып. 38. М.: Наука. 1965. С. 5 108.

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

5. Липатов Е. П. Об одном случае наравномерного локального кодирования // Проблемы кибернетики, вып. 26, С. 95-107.

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

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

8. Нечипорук Э. И. О вентильных схемах // Международный симпозиум по теории релейных схем и конечных автоматов. Тез. док. М. 1962. С. 42-43.

9. Редькин Н. П. О реализации монотонных булевых функций контактными схемами // 4-я Всесоюзная конференция по проблемам теоретической кибернетики: Тез. докл. Новосибирск, 1977. С. 180-181.

10. Редькин Н. П. О реализации монотонных булевых функций схемами из функциональных элементов // Проблемы кибернетики. Вып. 35. М.: Наука, 1979. С. 87-110.

11. Резник В. И. О реализации монотонных функций схемами из функциональных элементов // ДАН СССР. 1961. 139. № 3. С. 566-569.

12. Угольников А. Б. О реализации монотонных функций схемами из функциональных элементов // Проблемы кибернетики. Вып. 31. М.: Наука, 1976. С. 167-185.

13. Чашкин А. В. О среднем времени вычисления значений булевых функций // Дискрет, анализ и исслед. операций. Вып. 1. 1997. Т. 3. № 1. С. 6078.

14. Чашкин А. В. Средняя сложность булевых функций // Дискретная математика и ее приложения, М.: Изд-во Центра прикладных исследований при механико-математическом факультете МГУ. 2001. С. 145-170.

15. Чашкин А. В. О сложности сужений булевых функций // Дис. д-ра. физ.-мат. наук, МГУ им. М. В. Ломоносова, мех.-мат. фак., М. 1999.

16. Чашкин А. В. Об одном методе вычисления частичных булевых функций // Математические вопросы кибернетики. Вып. 12, М.: Наука, 2004, С. 231-246.

17. Чашкин А. В. Средняя сложность симметрических булевых функций // Вестник МГУ. Сер. 1. Математика. Механика. 2003. № 1. С. 16-19.

18. Чашкин А. В. Об одном методе вычисления монотонных функций // Ломоносовские чтения. Секция: Математика, механика. 2004.

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

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

21. Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // УМН. 1957. 12. Вып. 6. С. 189-196.

22. Hansel G. Sur le nombre des fonctions booleannes monotones de n variables // C. R. Acad. Sci. Paris. 1966. 262. P. 1088-1099.

23. Kleitman D. On Dedekind's problem: the number of monotone Boolean Functions // Proc. of the Amer. Math. Soc. 1969. 21. № 3. P. 677-682.

24. Pippendger N. The Complexity of monotone-boolean functions // Math. Systems Theory. 1978. № 11. P. 289-316.

25. Pippendger N. On the evalution of powers and monomials. SIAM J. Comput. Vol 9, № 2, May 1980. P. 230-250.Публикации автора по теме диссертации

26. Забалуев Р. Н. О сложности реализации полиномов Жегалкина // Дискретная математика. Том 16. Вып. 1. 2004. С. 79-94.

27. Забалуев Р. Н. О средней сложности булевых функций, заданных полиномами Жегалкина // Дискрет, анализ и исслед. операций. Серия 1. 2004. Т. 11. №3. С. 3-15.

28. Забалуев Р. Н. О средней сложности полиномов Жегалкина // Материалы XIV Международной школы-семинара "Синтез и сложность управляющих систем". Н. Новгород. 2003. С. 38-43.

29. Забалуев Р. Н. О средней сложности функций из инвариантных классов // Материалы XIII Международного семинара "Дискретная математика и ее приложения". Москва. 2004. С. 66-69.

30. Забалуев Р. Н. О средней сложности вычислений монотонных функций // Материалы XV Международной школы семинара "Синтез и сложность управляющих систем". Новосибирск. 2004. С. 40-45.