С.Н. Селезнёва, А.Б. Дайняк, М.С. Шуплецов - Булевы функции и полиномы (1123636), страница 4
Текст из файла (страница 4)
n2 .Нижнюю оценку для rδ (n) получим мощностным методом. Число всех полиномов Жегалкина рангане больше r равноPrn2 i=0 ( i ) .Число функций, приближаемых с точность δ одним полиномом, равноbδ·2n c n Xi=01 Приэтом полагают 0 · log2 0 = 0 .2i.16ГЛАВА 3. РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ ОБОБЩЕННЫМИ ПОЛИНОМАМИnЧисло булевых функций от n переменных равно 22 , поэтому должно быть выполнено неравенствоPrδ (n)2i=0(ni) ·bδ·2n c n X2ii=0n> 22 .(3.11)По лемме 3, при достаточно больших nbδ·2n c n Xi=02in6 2·2 ,где < 1 . Поэтому при больши́х n для выполнения (3.11) необходимо, чтобы rδ (n) удовлетворялонеравенствуrδ (n) X n> (1 − ) · 2n .ii=0Это неравенство, в свою очередь, в силу леммы 2, влечетn − rδ (n)> 1 − .(n − 2rδ (n))2Решая это неравенство, получаемn 1+rδ (n) > −2p8(1 − )n + 1n& .8(1 − )2Объединяя верхнюю и нижнюю оценки, получаем rδ (n) ∼ 21 n . Теорема доказана.Лемма 4.
Для любого непустого множества S ⊆ E2n и любой функции f ∈ P2 (n) найдется полиномЖегалкина P , обладающий свойствами1. P совпадает с f на множестве S .2. Для любой ЭК K из P найдется набор αe ∈ S такой, что ind(K) = ind(eα) .Доказательство. Доказательство проведем индукцией по мощности множества S . Если S = {eα}, иind(eα) = {i1 , . .
. , ir }, то полагаем0, если f (eα) = 0,P =xi1 · . . . · xir , если f (eα) = 1.Пусть |S| = l+1 и утверждение леммы верно для всех множеств мощности 1 . . . , l . Пусть αe — такойe . По предположению существуетнабор из S , что не существует βe ∈ S , для которого ind(eα) ⊂ ind(β)полином P 0 , совпадающий с f на множестве S \ {eα} . Пусть ind(eα) = {i1 , . . . , ir }. Нетрудно видеть,что полиномP 0 , если f (eα) ⊕ P 0 (eα) = 0,P =0xi1 · . .
. · xir ⊕ P , если f (eα) ⊕ P 0 (eα) = 1.удовлетворяет всем свойствам из утверждения леммы.Следствие 3.3. При δ ∈ [0, 1] справедлива оценка lδ (n) 6 (1 − δ) · 2n + 1 .Доказательство. Пусть f ∈ P2 (n) — произвольная функция. Выберем произвольное множествоS ⊆ E2n мощности d(1 − δ) · 2n e . По лемме 4, существует полином P , совпадающий с f на S . Нетрудно видеть, что P имеет длину не больше d(1 − δ) · 2n e 6 (1 − δ) · 2n + 1 . Кроме того, P реализует f сточностью δ , поскольку совпадает с f по крайней мере на d(1 − δ) · 2n e наборах.3.2. ПРИБЛИЖЕННАЯ РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ17Оценку, которую дает это следствие, можно, оказывается, улучшить вдвое, о чем утверждает следующая теорема.Теорема 3.6 ([6]).
lδ (n) = 1 при δ > 12 .lδ (n) = 2n при δ = 0.lδ (n) 6 21 (1 − δ) · 2n + 1 при δ ∈ (0, 12 ) .Доказательство. Разбор случаев δ > 12 и δ = 0 предоставляется читателю.Пусть δ ∈ (0, 12 ), и f ∈ P2 (n) — произвольная функция. Пусть l0 = d(1 − δ) · 2n + 1e . Построиммножество S по правилу: сначала в S добавим набор e0 , затем все набора ранга 1 , все наборы ранга 2 ,и т.д., пока не наберем l0 наборов. При этом если r — максимальный ранг наборов, то S необязательносодержит все наборы ранга r .
Множество S обладает тем свойством, что для всякого набора из S всенаборы меньшего ранга также принадлежат S . По лемме 4, существует полином P , совпадающий с fна S , длина которого не превосходит l0 . Возможны два случая:l(P ) 6 21 l0 . Нетрудно видеть, что по выбору l0 , полином P реализует f с точностью δ .l(P ) > 12 l0 . Рассмотрим функцию h(exn ) = x1 · . . . · xn .
Полином Жегалкина Ph для этой функции содержит все монотонные ЭК от переменных x1 , . . . , xn . Пусть Ph0 — полином, полученный изPh отбрасыванием всех ЭК, соответствующих наборам из E2n \ S . Очевидно, что в силу структурымножества S , полином Ph0 реализует функцию, совпадающую с h на S . Но функция h принимает значение 1 только на нулевом наборе. Следовательно, и значение Ph0 отличается на S от нуля только нанаборе e0. Рассмотрим полином P 0 = P ⊕ Ph0 . Этот полином имеет длину 6 12 l0 и реализует функцию,совпадающую с f на множестве S \ {e0} мощности (l0 − 1).Итак, в любом случае, можно построить полином длины не больше 12 d(1 − δ) · 2n + 1e 6 21 (1−δ)·2n +1 ,реализующий функцию, совпадающую с f на множестве мощности не меньше d(1 − δ) · 2n e . Этот полином будет, очевидно, реализовывать f с точностью δ .Глава 4Распознавание свойств функций,заданных полиномами4.1Постановка задачиРассмотрим задачу следующего вида.
Пусть нам дана функция f ∈ P2 (n) и некоторое свойство P .Требуется ответить на вопрос: обладает ли f свойством P . Данная глава посвящена оценке сложностиалгоритмов, позволяющих решать описанную задачу для фиксированного P . Наиболее естественнымисвойствами функций является их принадлежность замкнутым классам в P2 , и, прежде всего, предполным замкнутым классам.Проблема получения оценок сложности алгоритмов определения принадлежности функций предполным классам хорошо изучена для случая, когда функции заданы своими векторами значений.
Мыже будем рассматривать алгоритмы, на вход которых подается в некоторой кодировке полином Жегалкина функции, свойства которой нужно определить. Обозначим через AP (n, l) алгоритм, которыйпринимает на вход полином Жегалкина длины l некоторой функции f ∈ P2 (n), и на выходе даетответ «да» или «нет» в зависимости от того, обладает ли f свойством P .Как и ранее, для функции f через Pf будем обозначать полином Жегалкина, реализующий f .Через l(P ) будем обозначать длину полинома P . Введем функции сложности:LA (f ) — число элементарных операций, которое нужно произвести в соответствии с алгоритмомA = AP (n, l) для распознавания свойства P функции f ∈ P2 (n) , задаваемой полиномом длины l .LA (l) = maxl(Pf )=l lA (f ) — максимальное число элементарных операций, достаточное для распознавания алгоритмом A свойства P функции, заданной полиномом длины l .В связи с тем, что мы рассматриваем только полиномы Жегалкина, и, соответственно, толькомонотонные ЭК, мы будем отождествлять ЭК со множествами входящих в них переменных (то естьс индексами этих ЭК).
При получении оценок для функции LA (l) будем рассматривать формальнуюалгоритмическую модель, содержащую следующие элементарные операции:• операции присваивания• подстановка констант в заданную ЭК вместо некоторых переменных• оператор условного присваивания• операции над ЭК как над множествами переменных, т.е. операции вида K := K1 ∪ K2 ,K := K1 ∩ K2 , K := K1 \ K2• операции сравнения ЭК как множеств переменных: K1 ⊂ K2 ? , K1 ⊆ K2 ? , K1 = K2 ? и т.д.Сложность алгоритма равна суммарному числу элементарных операций, выполняемых алгоритмом дополучения ответа в худшем случае.184.2.
РАСПОЗНАВАНИЕ МОНОТОННОСТИ19Описанная алгоритмическая модель может показаться искусственной, однако нетрудно видеть, чтополиномиальные верхние оценки сложности алгоритмов в данной модели приводят к полиномиальнымверхним оценкам в известных стандартных моделях, например, в классе схем из функциональных элементов (СФЭ), или в классе машин Тьюринга. Вполне естественно исследовать, прежде всего, свойствафункций, определяющих их принадлежность предполным классам Поста. Очевидно, распознать линейность функции, а также свойства сохранения нуля и единицы, по полиному Жегалкина можно залинейное время.
Нетривиальным остается только распознавание монотонности и самодвойственностифункций по их полиномиальным представлениям. Этому и посвящены следующие два параграфа.4.2Распознавание монотонностиЦель этого параграфа — построить алгоритм распознавания монотонности функций, задаваемых полиномами фиксированной длины. Напомним, что функция f называется монотонной, если для любыхe .
Набор αнаборов αe, βe таких, что αe 6 βe , выполнено f (eα) 6 f (β)e называется нижней единицей функe = 0 для всякого набора βe 6 αции f , если f (eα) = 1 и f (β)e . Везде далее будем рассматривать всякоемножество монотонных ЭК K1 , . . . , Kl как частично упорядоченное, с отношением порядка, порожденным отношением включения на множестве {ind(K1 ), . . . , ind(Kl )} . В связи с этим будем говоритьо минимальных и максимальных элементах во множестве K1 , .
. . , Kl . Докажем вспомогательнуюлемму.Лемма 5. Пусть f ∈ P2 (n) задана полиномом Жегалкина Pf = K1 ⊕ . . . ⊕ Kl . Пусть Ki1 , . . . , Kim —все минимальные элементы во множестве {K1 , . . . , Kl } . Тогда между множеством {Ki1 , . . . , Kim }и множеством всех нижних единиц функции f можно установить взаимно однозначное соответствие. При этом ЭК Kij соответствует нижняя единица αej такая, что ind(eαj ) = ind(Kij ) .Доказательство. Пусть Kij ∈ {Ki1 , .
. . , Kim } . Тогда на наборе αej таком, что ind(eαj ) = ind(Kij )слагаемое Kij в Pf обращается в единицу, а все остальные слагаемые равны нулю. Таким образом,f (eαj ) = 1 . При этом для всякого набора βe , меньшего αej , слагаемое Kij обнуляется, и все остальныеeслагаемые по-прежнему равны нулю, значит f (β) = 0. Таким образом, αej является, по определению,нижней единицей f .Пусть теперь αe — какая-то нижняя единица функции f .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
