О средней сложности булевых функций

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

Рассматриваемые программы были введены А. В. Чашкиным [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{xt) внутренних переменных 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{xtk), если 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^Oztr) V. s°r (x)z (xL). где суммирование производится по всем двоичным наборам длины п, назовем средним временем работы программы Р. Если для некоторой булевой функции / и любого двоичного набора х справедливо равенство 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 (/) 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.