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

. · xm .m000Заметим, что s{0,m } ∈/ {s{0,m } }y при m0 6= m00 , и, следовательно, для различных{0,m}множеств J, J ⊆ N \ {1}, соответствующие им множества функций QJ = { sm|m ∈ J }y будут различны. Очевидно, что каждое из указанных множеств являетсяb и, следовательно, имеет харакинвариантным классом, содержащимся в классе S,теристику 0. Классов QJ будет столько же, сколько подмножеств имеет множествоN \ {1}, то есть континуум.Лемма доказана.Множество F называется базовым множеством инвариантного класса Q, если Fy = Q.

Базовое множество класса Q называется базой, если любое его собственное подмножество уже не является базовым множеством для Q. Существуют инвариантные классы, не имеющие базы. Например, класс, состоящий из констант 0, 1и всех монотонных элементарных дизъюнкций (функций вида xi1 ∨ · · · ∨ xis ), имеетсчётное базовое множество, но не имеет базы.Для задания всякого инвариантного класса достаточно задать, таким образом, его базовое множество. Существует и другой способ задания инвариантныхклассов. Пусть Q — нетривиальный отличный от P2 инвариантный класс. Функция g ∈ P2 называется порождающим элементом класса Q тогда и только тогда,когда g ∈/ Q, а все собственные подфункции1 g принадлежат Q.

Из определения1Под собственной подфункцией функции g понимается её произвольная подфункция, не совпадающая с g.48Глава 1.следует, что порождающий элемент нетривиального инвариантного класса является существенной функцией и что никакие два различных порождающих элементане являются квазиподфункциями друг друга. Приведём примеры порождающихэлементов. Класс M монотонных ФАЛ имеет единственный с точностью до конгруэнтности порождающий элемент — функцию x1 .

Для инвариантного класса Qего порождающим множеством называется всякое максимальное по включениюмножество попарно не конгруэнтных порождающих элементов Q. Так, порождающее множество класса, состоящего из констант и монотонных элементарных дизъюнкций, суть {x1 , x1 x2 }.Лемма 8.5. Пусть Q — нетривиальный отличный от P2 инвариантный класс,а G — его порождающее множество.

Тогда Q = P2 \ (Gq ).Доказательство. Индукцией по n, n = 1, 2, . . . , докажем, что если f — существенная ФАЛ от n БП и f ∈/ Q, то G ∩ ({f }y ) 6= ∅. Заметим, что данное утверждениеверно, если любая собственная подФАЛ ФАЛ f прининадлежит Q. Действительно, в указанном случае ФАЛ f является порождающим элементом Q и в G имеетсяконгруэнтная ей ФАЛ. Это верно, в частности, для случая n = 1, который составляет базис рассматриваемой индукции.Пусть сформулированное утверждение верно для всех n, n ∈ [1, k), где k > 2,и пусть f — существенная ФАЛ из P2 (k) \ Q(k), которая (см. разобранный вышеслучай) имеет собственную подФАЛ f 0 , f 0 ∈/ Q.

Тогда, по индуктивному предполо0жению G ∩ ({f }y ) 6= ∅ и, следовательно, G ∩ ({f }y ) 6= ∅, так как первое из этихмножеств содержится во втором.Лемма доказана.Следствие. Пусть множество G состоит из ФАЛ, не являющихся квазиподфункциями друг друга. Тогда P2 \ (Gq ) — инвариантный класс с порождающиммножеством G.§9Принцип локального кодирования О. Б. Лупанова и примерыего применения.Рассмотрим достаточно общий подход к решению задачи синтеза СФЭ для ФАЛиз специальных классов, предложенный в работе [5] О.

Б. Лупанова и названныйим принципом локального кодирования.Основаная идея этого подхода состоит в том, чтобы с помощью определённого«кодирования» свести задачу синтеза СФЭ для ФАЛ или операторов из заданногокласса Q к аналогичной задаче синтеза для класса произвольных или близких кним операторов соответствующей размерности. В [5] был предложен ряд условий,налагаемых как на класс Q, так и на его кодирование, при выполнении которыхполучаемые указанным способом схемы могли оказаться асимптотически наилучшими как для самых «плохих» ФАЛ (систем ФАЛ) из Q(n), так и для почти всех§9.

Принцип локального кодирования О. Б. Лупанова49ФАЛ (систем ФАЛ) из Q(n), n = 1, 2, . . . . Следующее утверждение и его доказательство дают пример решения задачи синтеза СФЭ для ФАЛ из инвариантногокласса Q с помощью принципа локального кодирования.Лемма 9.1. Для всякого инвариантного класса Q и n = 1, 2, . . .2nLC Q(n) ∼ σQn 2n CL Q(n) = o σQnпри σQ > 0,(9.1)при σQ = 0.(9.2)Доказательство. Рассмотрим сначала случай σQ > 0. В этом случае в соответствии с введёнными в §8 обозначениями и в силу леммы 8.3 получимJ Q(n) =σQ (n) · 2nlog |Q(n)|2n=∼σ,Qlog log |Q(n)|log(σQ (n) · 2n )nоткуда по лемме 8.1 следует нижняя оценка (9.1).Перейдём к получению верхней оценки (9.1). Для этого возьмём произвольноенатуральное n и натуральное q, q 6 n, а затем обычным образом разобьём наборБП x = (x1 , .

. . , xn ) на поднаборы x0 = (x1 , . . . , xq ) и x00 = (xq+1 , . . . , xn ). Выберемиз множества Q(n) произвольную ФАЛ f и для каждого набора σ 00 , σ 00 ∈ B n−q (x00 ),положим как обычно, fσ00 (x0 ) = f (x0 , σ 00 ), причём в данном случае fσ00 (x0 ) ∈ Q(q) всилу инвариантности класса Q.Положим λ = dlog |Q(q)|e и пусть Π0 — произвольное инъективное отображение (кодирование) ФАЛ множества Q(q) двоичными наборами куба B λ от БП y =(y1 , . . . , yλ ), то есть Π0 : Q(q) 7→ B λ (y), которое существует, так как 2λ > |Q(q)|.

Заметим, что ФАЛ fσ00 (x0 ) однозначно определяется своим «кодом» πσ00 = Π0 (fσ00 (x0 ))и поэтому существует ФАЛ h(x0 , y), h ∈ P2 (q + λ), такая чтоf (σ 0 , σ 00 ) = h(σ 0 , πσ00 )при любых σ 0 и σ 00 из B q (x0 ) и B n−q (x00 ) соответственно.Пусть O = (O1 , . . . , Oλ ) ∈ P2λ (n − q) — система ФАЛ, которая сопоставляетпроизвольному набору σ 00 , σ 00 ∈ B n−q , набор («код») πσ00 и пусть СФЭ ΣO из UC ,построенная асимптотически наилучшим методом, реализует эту систему ФАЛ сосложностью 2n−q 2n−qL ΣO 6 λ+o.n−qn−qИскомая СФЭ Σf реализует ФАЛ f в соответствии с представлениемf (x0 , x00 ) = h(x0 , O(x00 ))и содержит в качестве подсхемы СФЭ ΣO (x00 , y), а также построенную асимптотически наилучшим методом СФЭ Σh , которая реализует ФАЛ h(x0 , y).50Глава 1.Полагая q = dlog ne, и учитывая, чтоλ 6 σQ (q)2q + 1 .

σQ 2q ,получим верхнюю оценку2n−q2nL Σf . σQ 2q. σQ .n−qnВ случае σQ > 0 отсюда, с учётом нижней оценки, вытекает (9.1).В случае σQ = 0 искомая СФЭ Σf строится аналогично, но так как при этомполседовательность σQ (q) стремится к нулю, то 2n L Σf = o,nчто доказывает (9.2).Лемма доказана.Как уже говорилось, при доказательстве верхней оценки леммы 9.1 мы фактически использовали приём, называемый принципом локального кодирования, предложенный О. Б.

Лупановым, который состоит в следующем. Пусть Q — класс операторов, и пусть для каждого натурального n определено кодирование Π = Πn ,ставящее в соответствие произвольному оператору F = Fn , F ∈ Q(n), двоичныйнабор («код») π = π(F ) длины d = d(n), в котором выделены «куски» πi , i ∈ [1, t],составленные из подряд идущих разрядов кода π и имеющие длину не больше,чем λ = λ(n). Пусть указанное кодирование обладает свойством «локальности»:для вычисления значения оператора F на произвольном фиксированном наборе σдостаточно знать лишь один кусок кода πi(σ) , задаваемый своими «координатами»(например, позицией его первого разряда в коде и длиной, или номером куска, есликуски кода не пересекаются и имеют одинаковую длину, и т.п.).(1)Пусть, далее, оператор кодирования A(1) = An по набору σ вычисляет ко(2)ординаты куска кода πi(σ) , а оператор декодирования A(2) = An по куску πi(σ)и, возможно, набору σ, вычисляет F (σ).

Искомая схема Σ = Σn , реализующаяоператор F и построенная на основе локального кодирования Π, состоит из подсхем A(1) , A(2) и «основного» блока O = On , который по координатам куска πi(σ)выдаёт сам этот кусок.(1)(2)Если при этом сложность указанных выше операторов An , An и On удовлетворяет соотношениям(1)(2)LC= o J Q(n) ,LC= o J Q(n) ,(9.3)Б AnБ AnLC(9.4)Б On . ρБ · J Q(n) ,то искомая СФЭ Σn может быть выбрана так, чтоL Σn .

ρБ · J Q(n) .§9. Принцип локального кодирования О. Б. Лупанова51Отсюда вытекает, чтоLCБ Q(n) . ρБ · J Q(n) ,и, следовательно, в силу леммы 8.1 в случае невырожденности класса Q выполняется асимптотическое равенствоLCБ Q(n) ∼ ρБ · J Q(n) ,которое означает стандартность класса Q относительно функционала сложности Lкласса схем UCБ.Заметим, что в случае асимптотической неизбыточности кодирования Π = Πn ,когдаd(n) ∼ log |Q(n)|,при построении схемы, которая реализует оператор On со сложностью, удовлетворяющей (9.4), достаточно, как правило, использовать асимптотически наилучшийметод синтеза СФЭ для произвольных систем ФАЛ подходящей размерности илинекоторые его модификации (см., например, лемму 8.2).Заметим также, что соотношение (9.3) означает возможность существенно бо(1)(2)лее простой по сравнению с оператором On реализации операторов An и An вклассе UCБ.Покажем, что описанный в доказательстве леммы 9.1 асимптотически наилучший метод синтеза СФЭ над базисом Б является примером применения принципалокального кодирования.Действительно, в обозначениях данного доказательства, локальное кодирование Π сопоставляет произвольной ФАЛ f, f ∈ Q(n), код π длины d = λ · 2n−q ,разбитый на 2n−q непересекающихся кусков длины λ и вида πσ00 , где σ 00 ∈ B n−q .При этом оператор кодирования A(1) представляет собой оператор выбора поднабора x00 из набора x, оператор O совпадает с оператором O, а оператор A(2) — сФАЛ h.Рассмотрим ещё два класса операторов и с помощью принципа локального кодирования докажем (при некоторых условиях) их стандартность.

Обозначим через S класс всех симметрических ФАЛ, а под (n, m)-оператором будем пониматьсистему ФАЛ F = (f1 , . . . , fm ) из P2m (n).Лемма 9.2. Если натуральная последовательность m = m(n), n = 1, 2, . . . , такова, чтоlog n = o(m) и log m = o(n),(9.5)то класс операторов Q, для которого Q(n) = S m (n), является невырожденными стандартным относительно функционала сложности L СФЭ из UC классомоператоров.52Глава 1.Доказательство. Для рассматриваемого класса операторов Q при любых натуральных n и m выполняется равенство |Q(n)| = 2m(n+1) , из которого следует, чтоJ (Q(n) =m(n + 1).log m + log(n + 1)(9.6)Из (9.6), в свою очередь, вытекает, что последовательностиmlog m + log(n + 1)log m=6+ o(1),n+1nJ Q(n)nlog m + log(n + 1)log n66+ o(1)mmJ Q(n)в силу (9.5) стремятся к 0 при n стремящемся к бесконечности и, следовательно,m + n = o(J(Q(n)), то есть Q(n) — невырожденный класс операторов. Отсюда полемме 8.1 с учётом (9.5) получаем нижнюю оценку m·nLC Q(n) & J Q(n) ∼.(9.7)log nДля получения аналогичной вехней оценки рассмотрим кодирование Π = Πn ,которое оператору F, F ∈ Q(n), сопоставляет набор π(F ) = π длины d = m(n + 1)и вида π = ( F (0, .