Материалы для подготовки к экзамену (2012-2013 учебный год), страница 12

Действительно, при r = 1это очевидно, а при увеличении числа r на 1 мощность множества A00 увеличивается не больше, чем на 1. Таким образом, множество A0 = A \ A00 разделяетсяоператором ψ и имеет требуемую мощность.Лемма доказана.Следствие. Если в условиях леммы s > b2 log tc, то A0 = A, так как|A0 | > t −t(t − 1)> t − 1.2s+1Лемма 10.4. Если 2n/3 6 t 6 2n /n5 , тоLC Pb2 (n, t) .t.log tДоказательство. Положим s = blog t + 2 log n + log log tc и заметим, что в силуусловий леммы выполняются соотношенияs 6 n,s ∼ log t,nt log t = o(2s ).(10.8)Возьмём произвольную фунцию f , f ∈ Pb2 (n, t), и пусть A = δ(f ), |A| = t. Построим по лемме 10.3 для множества A, A ⊂ B n , оператор ψ, который отображаеткуб B n от БП x = (x1 , .

. . , xn ) в куб B s от БП y = (y1 , . . . , ys ) и разделяет подмножество A0 , A0 ⊆ A, такое, что|A0 | = t0 > t −t(t − 1).2s+1Заметим, что при этом в силу (10.8) t0 ∼ t, s ∼ log t0 , и следовательно, длямножества Pb2 (s, t0 ), которому принадлежит функция fe0 (y) такая, что δ(fe0 ) = ψ(A0 )58Глава 1.и fe0 (ψ(α)) = f (α) при любом α, α ∈ A0 , выполнены условия леммы 10.2.

Найдёмпо этому утверждению такое доопределение ge0 (y) ФАЛ fe0 (y), для которогоLC (eg0) .t0t∼.0log tlog t(10.9)Легко видеть, что ФАЛ видаg(x) = ge0 (ψ(x)) · x (x) ∨ g 00 (x),00где(10.10)x00 – характеристическая ФАЛ множества A00 = A \ A0 , а g00 — ФАЛ, совпадаю-щая с f на A00 и равная 0 вне его, является доопределением ФАЛ f .

Заметим, чтореализация ФАЛ x00 и g 00 по их совершенным ДНФ даёт следующую суммарнуюоценку их сложностиLC ( x00 ) + LC (g 00 ) = O(nt2 /2s ),а известная оптимальная реализация линейной ФАЛ — оценкуLC (ψ) 6 4ns,из которых в силу (10.8) вытекает оценкаLC ( x00 ) + LC (g 00 ) + LC (ψ) = o(t/ log t).(10.11)Таким образом, реализуя ФАЛ g(x) в соответствии с (10.10) и учитывая (10.9), (10.11), получимtLC (f ) ..log tЛемма доказана.Лемма 10.5. Если t 6 2n/3 и n log2 n = o(t), тоLC Pb2 (n, t) .t.log tДоказательство этого утверждения представляет собой упрощённый вариант доказательства леммы 10.4, при котором s = b2 log tc и, следовательно, A0 = A, то естьвариант, не требующий реализации ФАЛ x00 , g 00 .Суммируя доказанные утверждения, получаем следующий основной результат.Теорема 10.1.

Если n log2 n = o(t), тоLC Pb2 (n, t) ∼t.log tЗамечание. Оценка теоремы верна и при более слабом условии n log n = o(t) [2].Глава 2Синтез схем для индивидуальных функций и оценки ихсложности§1Средняя проводимость схемы. Асимптотика контактной сложности универсальных систем функцийИспользование так называемой средней проводимости контактов схемы позволяетв некоторых случаях получать более высокие по сравнению с леммой 2.3 [3, глава 4]нижние оценки сложности реализации систем ФАЛ в классе UК .

Этот метод ужеприменялся, по существу, при доказательстве минимальности контактного деревав классе разделительных КС (см. лемму 2.5 [3, глава 4]).Будем называть множество δ, δ ⊆ B n , равномерным, если для каждого i,i ∈ [1, n], число тех наборов α = (α1 , . . . , αn ) из δ, у которых αi = 1, равно |δ|2 .Заметим, что каждый контакт КС Σ = Σ(α1 , . . . , αn ) проводит (не проводит) ровно на половине всех наборов равномерного множества δ, δ ⊆ B n , и, следовательно,в обозначениях §§1, 5 [3, глава 2] выполняются равенства1 X1 X1|E(Σ|α )| =|E(Σ|α )| = L(Σ)(1.1)|δ||δ|2α∈δα∈δкоторые и задают «среднюю» проводимость (непроводимость) контактов Σ на наборах множества δ. В качестве множества δ мы, чаще всего, будем выбирать весьединичный куб B n , а для получения нижних оценок сумм (1.1) — использоватьнеравенства|E(Σ|α )| > |V (Σ)| − |c(Σ|α )|,(1.2)|E(Σ|α )| > |c(Σ|α )| − |C(Σ)|,(1.3)которые вытекают из неравенства (1.2) [3, глава 2].

Напомним, что в [3, глава 4]было доказано следующее утверждение.Лемма 1.1. Если система ФАЛ F = (f1 , . . . , fm ) состоит из попарно различныхи отличных от констант ФАЛ от БП X(n), тоLК (F ) > 21−nmXNf .jj=15960Глава 2.Следствие 1.LК (Jn ) > 2n+1 − 2Следствие 2. Оценки следствия 1 и леммы 7.3 из [3, глава 4] дают асимптотическое равенство→− LК J n ∼ 2n+1Теорема 1.1. Для любого множества ФАЛ Q, Q ⊆ P2 (n), и любого натурального r, r 6 n, справедливо неравенство −5К →b ,L Q > 2|Q| 1 − √− 2Q(1.4)rb состоит из тех ФАЛ f , f ∈ Q, у которых во множестве N fгде множество Qесть грани размерности больше, чем (n − r).Доказательство. Пусть Σ — минимальная приведённая (1, |Q|)–КС, реализующая→−систему ФАЛ Q , и пусть V — множество её выходных вершин.

Пусть, далее, sи t — натуральные параметры, для которых (s − 1)(t − 1) 6 r, а V 0 — множество техвыходных вершин Σ, степень которых не меньше, чем s. Достаточно рассмотретьслучай, когда|Q||V 0 | 6 4,(1.5)sтак как иначе число контактов Σ инцидентных вершинам из V 0 уже было бы неменьше, чем 2|Q|.Для произвольного набора α, α ∈ B n , множество c(α) связанных компонентсети Σ|α разобьём на непересекающиеся подмножества ci (α), i ∈ [1, 4], так, чтосвязная компонента G, G ∈ c(α), входит в подмножество:1.

c1 (α), если V (G) * V ;2. c2 (α), если G ∈/ c1 (α) и V (G) ∩ V 0 6= ∅;3. c3 (α), если G ∈/ (c1 (α) ∪ c2 (α)) и |V (G)| > t;4. c4 (α) в остальных случаях.Заметим, что произвольная связная компонента G из ci (α) удовлетворяет неравенству|E(G)| > |V ∩ V (G)|,(1.6)если i = 1 и состоит только из выходных вершин Σ в остальных случаях. При этомв случае i = 2 она содержит хотя бы одну вершину из V 0 , в случае i = 3 — состоитне менее, чем из t вершин, а в случае i = 4 включает в себя не более (t − 1) вершин,которые отделяются от остальных вершин сети Σ|α сечением, состоящим не более,§2.

Сложность линейной функции в классе СФЭ61чем из (s − 1)(t − 1) 6 r, контактов множества E|Σ|α |. Таким образом, в каждойb и,вершине компоненты G из множества c4 (α) реализуется ФАЛ из множества Q,учитывая все вышесказанное, получим|c2 (α)| 6 |V 0 |,|c3 (α)| 6|Q|,tb|c4 (α)| 6 |Q|.(1.7)Из (1.5)–(1.7) в силу (1.2) вытекает неравенство4|Q| |Q|b−− |Q|,st√из которого в соответсвии с 1.1 при δ = B n и s = t = d r e следует (1.4).Теорема доказана. Следствие 1.

Полагая Q = P2 (n) и учитывая то, что при r = n2 множествоb = Pb2 (n) удовлетворяет соотношению Pb2 (n) = o 22n /√n , получимQ−1К →2n.L P 2 (n) > 2 · 21−O √n|E(Σ|α )| > |Q| −Следствие 2. Оценки следствия 1 и леммы 3.1 из[3, глава 4] дают асимптотическое неравенство→−nLК P 2 (n) ∼ 2 · 22 .§2Забивание переменных константами.

Сложность линейнойфункции в классе схем из функциональных элементовОпределим сначала операцию подстановки констант вместо переменных в функциии схемы. Будем считать, что любая ЭК K ранга r от БП X(n) вида K = xσi11 . . . xσirrзадаёт подстановку констант xi1 = σ1 , . . . , xir = σr . Результат применения указанной подстановки к системе ФАЛ F , F ∈ P2m (n), и схеме Σ от БП X(n) будемобозначать через F |K и Σ|K соответственно.

При этом система ФАЛ F |K определяется обычным образом, а преобразование схемы Σ в схему Σ|K в классе UC(UК ) связано с заменой вершин xij , j = 1, . . . , r, константой σj и применением, дотех пор, пока это возможно, тождеств подстановки констант из §§ 1–2 [3, глава 3]σ(соответственно отождествлением концевых вершин контактов вида xijj и удалеσнием контактов вида xijj , j = 1, . . . , r) с последующим переходом к эквивалентнойприведённой схеме. Заметим, чтоK · f = K · f |Kдля любой ФАЛ f и что схема Σ|K реализует систему ФАЛ F |K , если схема Σреализует систему ФАЛ F . Заметим также, что для КС Σ от БП X(n) и набора62Глава 2.α = (α1 , .

. . , αn ) схема Σ|xα1 ...xαnn в отличие от сети Σ|α (см. §§ 1,5 из [3, глава 2])1состоит из (кратных) изолированных полюсов.Те СФЭ из класса UC , которые реализуют линейные ФАЛ ln или ln , будемназывать линейными схемами порядка n. ПоложимL(n) = min{LC (ln ), LC (ln )},а линейные СФЭ порядка n и сложности L(n) будем называть минимальнымилинейными СФЭ. Из [3] (см.

лемму 3.1 гл. 4) следует, что если n > 2, тоL(n) 6 min{LC (ln ), LC (ln )} 6 4n − 4,(2.1)а из теоремы 3.1 в силу незабиваемости множества всех БП линейной ФАЛ вытекает, чтоL(n) > 2n − 2.Докажем, что верхняя оценка (2.1) даёт точные значения сложностей LC (ln )и LC (ln ).Лемма 2.1. Пусть Σ — линейная СФЭ порядка n от БП X(n) и пусть её БП xiпоступает только на вход ФЭ E СФЭ Σ, связанного с вершиной v. Тогда в случаеE = & (E = ∨) на второй вход ФЭ E поступает ФАЛ 1 (соответственно 0), ав случае E = ¬ СФЭ Σ0 , которая получается из Σ удалением E и объявлением vвходной вершиной БП xi , также является линейной СФЭ порядка n.Доказательство. Из свойств линейной ФАЛ следует, что СФЭ Σ0 отрицание тойФАЛ, которую реализует СФЭ Σ, и потому СФЭ Σ0 тоже является линейной СФЭпорядка n.Пусть теперь E — двухвходовой ФЭ, который соответствует ФАЛ ϕ(y1 , y2 ), ипусть на второй вход E поступает дуга из вершины w.

При этом ФАЛ g, котораяреализуется в вершине w, не зависит, очевидно, от БП xi . Предположим, что g 6≡ σ,где σ = 0 в случае ϕ = y1 · y2 и σ = 1 в случае ϕ = y1 ∨ y2 , то есть g|K =αi−1 αi+1σ для некоторой ЭК K вида xα1 1 . . . xi−1xi+1 . . . xαnn . Тогда в силу особенностейструктуры СФЭ Σ и в силу тождества ϕ(σ, xi ) = σ СФЭ Σ|K реализует константу,что противоречит линейности Σ.Лемма доказана.Следствие 1. Степень любого входа минимальной линейной СФЭ порядка n, n >2, не меньше двух.Следствие 2. Справедливы равенстваL(2) = LC (l2 ) = LC (l2 ) = 4.(2.2)§2.

Сложность линейной функции в классе СФЭu1 6= vx1•∨•w1u2 6= vx2••&•v•∨•w2• v 0a)63x1x2••∨w•x&•&v••b)Рис. 2.1:Действительно, в соответствии со следствием 1 ранг любой линейной СФЭ порядка 2 не меньше четырех. Поэтому в силу того, что в Σ есть хотя бы один ФЭ ¬,справедливо неравенство L(Σ) > 4, из которого в соответствии с (2.1) вытекает (2.2).Теорема 2.1. Для любого натурального n, n > 2, выполняются равенстваL(n) = LC (ln ) = LC (ln ) = 4n − 4.(2.3)Доказательство. В силу (2.1) для доказательства (2.3) достаточно убедиться втом, чтоL(n) > 4n − 4.(2.4)Установим справедливость (2.4) индукцией по n, n = 2, 3, .