8.2.Оценки сложности сфэ.

Оценки функции Шеннона L(n) строятся из тех же соображений, что и оценки сложности задачи. Верхние оценки получаются путем построения конкретной СФЭ, реализующей функцию f(n). Для этого было разработано в 1950-е годя целое направление в дискретной математике – методы синтеза СФЭ. А вот нижние оценки получаются «из мощностных соображений».

Построим СФЭ, реализующую функцию f = . Перегруппируем множители, собрав в одном месте переменные с нулевыми степенями. Тогда, перенумеровав переменные, функцию можно переписать в виде

f = (x_i & . .. & x_k)& (х_к+1 Vх_к+2 V ...V х_п).

Заметим, что в этой формуле не более n операций. Значит, сложность схемы данной функции не превосходит n.

Выше мы рассматривали очевидный метод построения СФЭ по совершенной ДНФ функции. Их него сразу следует

Утв. L(n) ≤(n +1) 2ⁿ.

Замечание. На самом деле легко доказать, что L(n)≤ (n + 1) 2^n-1. Действительно, посмотрим на таблицу значений нашей функции и выясним, чего в ней больше: нулей или единиц. В зависимости от этого будем исполь­зовать, соответственно, СДНФ либо СКНФ. В самом худшем случае будет 2^n-i дизъюнкций или коньюнкций.

Дальнейшее улучшение позволяет избавиться и от множителя n. Построим по индукции СФЭ, которая будет реализовывать множество функций K_n - все конъюнкции со сложностью C(n).

Обозначим через K_n множество всех функций вида . Сейчас мы будем строить схему, которая реализует все функции из K_n. Сложность такой схемы обозначим C(n). При n = 1 получается схема без элементов. Предположим, что мы уже построили схему для всех множеств с номерами меньше n. Зафиксируем число k < n. Построим схему, реализующую все функции из K_n, используя в качестве подсхем две схемы: для K_k и для K_n-k.

Рассмотрим произвольную конъюнкцию:

(x_i & . .. & x_k)& (х_к+1 Vх_к+2 V ...V х_п).

Возьмём по одному выходу из схем для K_k и K_n-k, реализующие множители в скобках, и подключим их к конъюнктору. Получим схему, реализующую одну конъюнкцию от n переменных. Также поступим со всеми 2ⁿ конъюнкциями от n переменных, то есть будем строить их, используя соответствующие выходы в схемах K_k и K_n-k, связывая их конъюнктором. Итого получим схему для K_n, затратив C(k)+C(n — k)+2ⁿ элементов. Теперь возьмём к := n/2 и получим С(п) ≤2ⁿ +2С(n/2) = 2ⁿ(2^n/2+2С(n/4))=2ⁿ+2^n/2+1+4С(n/4)) .

Отсюда следует, что можно (асимптотически) улучшить оценку для L(n): реализовав все конъюнкции ценой ~ 2ⁿ элементов, склеим их не более чем 2ⁿ дизъюнкциями, в итоге получим схему сложности порядка 2ⁿ⁺¹.

Дальнейшее улучшение в n раз дает метод Шеннона синтеза схем. Он просто использует разложение функции по k переменным

F(x₁,…,x_n) = .

Пусть k = n-q. Реализуем все конъюнкции K_k первых k переменных, при этом потратим 2^k элементов. Кроме этого, может потребоваться реализовать все функции от q переменных, которых всего . Каждую из них можно реализовать со сложностью q2^q. При склейке основной схемы по указанной выше формуле потребуется ещё 2^k конъюнкторов (для вычисления слагаемых) и ещё 2^k -1 дизъюнкторов. Итого

L(n) < 2^k + 2^k + (2^k — 1) + q 2^q < 3 • 2^k + q 2^q .

Положим q := [logn] — 1. Тогда

L(n) < 6•2^n-[logn] + n•logn•2^n/2-1 =12•2ⁿ / n + n•logn•2^n/2-1 < 12•2ⁿ / n .

Наконец, следующая теорема О.Б.Лупанова дает окончательную неулучшаемую асимптотическую оценку. Само доказательство взято из лекций О.Б.Лупанова.

Теорема. Справедливо соотношение L(n) < 2ⁿ / n .

Доказательство. Рассмотрим произвольную булеву функцию n переменных. Отделим q := n-k первых переменных и рассмотрим таблицу, в которой 2^k строк и 2^q столбцов. Строки занумеруем всевозможными значениями послед­них k переменных, а столбцы — всевозможными значениями первых q переменных. Ячейки таблицы заполним значениями функции. Каждый столбец представляет собой значения функции, полученной подстановкой кон­стант в первые q переменных, то есть . Разрежем таблицу на горизонтальные полоски по s строк в каждой (последняя полоса будет, возможно, меньше; пусть в ней s' < s строк). Число полос будет равно p=[2^k /s]< 2^k /s+1.

Через I_i обозначим индикатор i-й полосы, то есть функцию, которая равна единице на строках этой полосы, и только на них. Обозначим теперь

= I_i.

. Такие функции называются обрезанными функциями. Ясно, что

= .

Тогда имеем

f(x₁,…,x_n) = .

Реализуем все конъюнкции первых q переменных, потратив 2^q элементов. Кроме этого, реализуем все конъюнк­ции последних k переменных, потратив 2^k элементов. Все обрезанные функции имеют не более s ненулевых значений, значит, их количество не превышает 2^s. Поскольку все конъюнкции последних переменных уже есть, на изготовление СДНФ для каждой обрезанной функции уйдёт всего s дизъюнкций, значит, всего на реализацию обрезанных функций каждой полосы мы потратим не более s2^s элементов, а всего — не более ps 2^s.

На сборку каждой уйдёт ещё p дизъюнкций (поэтому всего на это уйдёт p 2^q операций), а на сборку функции f уйдёт ещё 2^q конъюнкций и 2^q дизъюнкций.

Суммируя полученные оценки, имеем

L(f) < 2^q + 2^k + ps2^s + p2^q + 2^q + 2^q = 3 2^q + ps 2^s + p2^q + 2^k.

Вспоминая, что р< 2^k /s+1, получаем

L(f) < 3 • 2^q +(2^k /s+ 1)(s2^s + 2^q) + 2^k.

Видно, что s должно быть порядка п, но всё же чуть меньше его. Что касается к, то нужно, чтобы 2^k /s→∞, чтобы нам не мешала единица в скобках. Положим k := [2 log n] и s := [n — 4 log n]. Подставляя эти значения, получаем оценку порядка 2ⁿ / n

Теорема доказана.

Чтобы доказать, что получена асимптотически неулучшаемая оценка, нужно аналогичную асимптотику L(n) > 2ⁿ / n снизу.

Пусть P* (n) — функции, существенно зависящие от n переменных. N(h, n) — число функций, существенно зависящих от n переменных, которые реализуются схемами слож­ности, не превосходящей h. N^'(h, n) — число функций, существенно зависящих от n переменных, которые реализуются схемами слож­ности ровно h; N^''(h, n) — число схем сложности h для функций, существенно зависящих от n переменных. Очевидно, что N^' = N, потому что всегда можно дополнить схему ничего не делающими элементами. Оче­видно также, что N≤N^'', так как одну функцию можно реализовать разными схемами, но не наоборот.

Покажем, что для любого ε>0, число функций, реализуемых схемами сложностью меньше (1 — ε ) 2ⁿ / n , гораздо меньше, чем всех функций. Итак, покажем, что для h_o= (1 — ε ) 2ⁿ / n выполнено соотношение N(h_o,n)<< |P*(n)|. Мы будем оценивать величину N, мажорируя её величиной N''.

Пусть y(p, q) — число графов с q ребрами и p= h + n вершинами (n входов и h элементов), N''(h, n, q) — число схем с q ребрами. Сколько схем можно сделать из одного графа? У нас имеется не более:

• 2^q способов выбрать ориентацию ребер;

• ( h + n) ⁿ способов выбрать входы;

• 3^h способов присвоения вершинам различных ФЭ;

• h + n способов выбора выхода.

Число γ(n,m) связных графов с n вершинами и m ребрами не превосходит

n^m-nconst^n+m. Действительно, чтобы из n-вершинного дерева сделать m-рёберный граф, нужно дополнительно провести ещё m—(n— 1)= k ребро. Из каждой вершины дерева можно выпустить куда-то ребро (так, чтобы второй конец пока не входил ни в какую вершину). Это можно сделать, очевидно, способами. Теперь эти концы надо как-то подсоединить к имеющимся вершинам. Это можно сделать mⁿ способами. Значит, существует не более

mⁿ mⁿ способов получить из дерева граф. А поскольку количество деревьев не превосходит 4^n-1, то в итоге имеем оценку сверху

4^n-1mⁿ 4^n-1mⁿ ≤4^n-1 2^mn^pm-n ≤ 8ⁿ8^m n^pm-n . Таким образом, достаточно взять const = 8.

Отсюда получаем:

N(h, n, q) ≤ γ(n,m) 2^q (h + n)ⁿ+¹ 3^h ≤ const^h+ⁿ+^q(h + n)^q—h+¹ 2^q 3^h. (15)

Вспоминая, что q ≤ 2h, и собирая константы в новую константуB , имеем:

N''(h, n, q)≤ B^3h+ⁿ(h + n)^h+¹.

Теперь получим оценку для N^''(n, h):

N''(h, n, q)≤ B^3h+ⁿ(h + n)^h+¹.

N''(n,h)≤ N''(h,n,q)≤ B^3h+ⁿ(h + n)^h+¹(h + 1) ≤ (C(h + n))^h+ⁿ.

Нам нужно убедиться, что N''(ho,n) < |P*(n)| при достаточно больших n. Заметим, что|P*(n)| > 2²" — n ≈ 2²". Таким образом, требуемое неравенство будет выполнено, если при n→∞ будет выполняться

Далее для достаточно боль­ших n:

log N’’(h_o,n) — 2ⁿ + o(1) ≤ (h_o + n) log(C(h_o + n)) — 2ⁿ + o(1)≤((1-ε)2ⁿ/n+n)n

-2ⁿ + o(l) = (1-ε)2ⁿ + n² - 2ⁿ + o(l) = n² + o(1) — ε2ⁿ →∞ при n→∞.

что и требовалось доказать.