С.Н. Селезнёва, А.Б. Дайняк, М.С. Шуплецов - Булевы функции и полиномы (1123636), страница 7
Текст из файла (страница 7)
· Kbi .(−2)s−1 K1s(5.10)16i1 <...<is 6lb i ·...·Kb i )=ind(eind(Kα)s1По лемме 10,Xwt(f ) =α|2n−|ebc(eα).(5.11)αe∈E2nИз (5.10) и (5.11) вытекает, чтоwt(f ) =Xαe∈E2nα|2n−|elXs=1X(−2)s−1 =16i1 <...<is 6lb i ·...·Kb i )=ind(eind(Kα)s1lXXs=1 16i1 <...<is 6l(−2)s−1 · 2n−r(Ki1 ·...·Kis ) .27Теорема 5.3 ([8]). Пусть k — фиксированное число. Существует детерминированный алгоритм,который по полиному Жегалкина булевой функции f (exn ) находит остаток от деления wt(f ) на 2kkсо сложностью O(l ), где l — длина полинома.Доказательство. Пусть функция f задана полиномом Жегалкина Pf = K1 ⊕. . .⊕Kl .
Непосредственно из леммы 11 следует, чтоwt(f ) ≡kXX(−2)s−1 · 2n−r(Ki1 ·...·Kis ) (mod 2k ).s=1 16i1 <...<is 6lТаким образом, для нахождения остатка от деления wt(f ) на 2k необходимо выполнить следующиедействия. Перебрать всевозможные конъюнкции вида Ki1 ·. . .·Kis не более чем k слагаемых полиномаPkPf (число таких конъюнкций равно s=1 sl ):a) для каждой из них определить r(Ki1 · . . . · Kis ) ;b) выполнить O(1) арифметических операций для вычисления (−2)s−1 · 2n−r(Ki1 ·...·Kis ) и добавитьэто число к общей сумме по модулю 2k .PkОчевидно, сложность приведенного вычисления равна O( s=1 sl ) = O(lk ). Теорема доказана.Описанный выше алгоритм позволяет при фиксированном k за полиномиальное время проверять,делится ли вес некоторой функции f ∈ P2 (n) на 2k .
Вопрос о том, существует ли решение аналогичной задачи за полиномиальное время в случае, когда k является параметром, зависящим от n , покаостается открытым. Например, представлял бы интерес полиномиальный алгоритм, отвечающий навопрос « wt(f ) = 2n−1 ?» (или доказательство того, что такого алгоритма не существует).Пример 5.2. Пусть f (ex3 ) = x1 x2 ⊕ x1 x3 ⊕ x2 x3 . Найдем остаток от деления wt(f ) на 2k при k = 2с помощью описанного в теореме 5.3 алгоритма. Промежуточное значение остатка будем хранить впеременной w . Вначале полагаем w := 0.1. Полином Pf состоит из трех ЭК ранга 2 .
Полагаемw := w + (−2)0 23−2 + (−2)0 23−2 + (−2)0 23−2 = 6 ≡ 2 (mod 22 ).2. Рассматриваем всевозможные произведения пар ЭК из Pf . Получаем три одинаковые конъюнкции x1 x2 x3 ранга 3 . Полагаемw := w + (−2)1 23−3 + (−2)1 23−3 + (−2)1 23−3 = −4 ≡ 0 (mod 22 ).Получаем, что wt(f ) без остатка делится на 22 .Литература[1] Гаврилов Г.
П., Сапоженко А. А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004. (Гл. 1, п. 3, с. 52-58)[2] Джавадов Р. М. О сложности приближенного задания функций алгебры логики. ДАН, т. 265, вып.1, 1982, с. 24-27.[3] Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций.Дискретная математика, т.
17, вып. 3, 2005, с. 80-88.[4] Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М., МЦНМО, 2004. (Гл. 2, п. 2.1-2.2, с. 65-90)[5] Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм. Алгебра и логика, 34, вып. 3, 1995, с. 323-326.[6] Селезнева С. Н. О приближении с заданной точностью функций многозначных логик полиномами.В печати.[7] Селезнева С. Н. О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина. Дискретная математика, т. 9, вып. 4, 1997, с.
24-31.[8] Селезнева С. Н. Об алгоритмической сложности нахождения остатка от деления на степеньдвойки веса булевой функции, заданной полиномом. Вестник МГУ. Серия 15 - Вычислительнаяматематика и кибернетика, т. 17, вып. 1, 2007, с. 32-36.[9] Яблонский С.
В. Введение в дискретную математику. М., Высшая школа, 2001. (Гл. 1, с. 9-42)[10] Carlet C., Guillot Ph. A new representation of Boolean function. Technical report, INRIA ProjectCODES, 1999, p. 1-14.[11] Even S., Kohavi I., Paz A. On minimal modulo 2 sums of products for switching functions. IEEE Trans.Elect. Comput., 1967, p.
671-674.Дополнительная литература[12] Айгнер М. Комбинаторная теория. М., Мир, 1982. (Гл. 4)28Оглавление1 Введение1.1 Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222 Полиномы Жегалкина и поляризованные полиномы2.1 Простейшие факты . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Сложность булевых функций в классе поляризованных полиномов . . . . . . . . . . . . .4463 Реализация булевых функций обобщенными полиномами3.1 Сложность булевых функций в классе обобщенных полиномов . . . . . . . . . . . . . . . .3.2 Приближенная реализация булевых функций .
. . . . . . . . . . . . . . . . . . . . . . . . .99134 Распознавание свойств функций, заданных полиномами184.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.2 Распознавание монотонности . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 194.3 Распознавание самодвойственности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Представление булевых функций полиномами над Z23Список литературы28.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
