Материалы для подготовки к экзамену прошлых лет, страница 3

. . , yp ) и любого разбиения∆ = (δ1 , . . . , δd ), где d 6 p, куба B n существуют ФАЛ gj (x, yj ) , j = 1, . . . , d,которые монотонно или антимонотонно завиясят от БП y1 , . . . , yd , а такжеФАЛ gs (x) , s = d + 1, . . . , t, такие, что ϕ (g1 , . . . , gt ) = µΔ (x, y1 , . . . , yd ).Доказательство.Теорема 3.1. Для любого натурального n ФАЛ µn (x, y) можно реализовать бесповторной по y формулой Mn , Mn ∈ UΦБ , гдеT (Mn ) 6 τБ n + O (1) ,(3.3)L (Mn ) 6 c · 2n .Доказательство.§4Задача синтеза схем для функций из специальных классов,примеры её решения и мощностные нижние оценки.

Инвариантные классы С. В. Яблонского, теорема о числе инвариантных классов.Для множества ФАЛ Q ⊆ P2 и натуральногого n через Q(n) будем обозначать множество Q ∩ P2 (n). При этом множество Q и связанную с ним последовательностьQ(1), Q(2), . . . будем называть классом ФАЛ. Аналогичным образом последовательность Q(1), . . . , Q(n), . . ., где Q(n) ⊆ P2m (n) и m = m(n), а также их объединение называется классом операторов. Пусть заданы класс ФАЛ или операторовQ, класс схем U и функционал сложности L. Тогда функцией Шеннона для Q, U, Lназывается функция натурального аргументаL(Q(n)) = max L(f ).f ∈Q(n)Для класса ФАЛ (операторов) Q введём функцииJ(Q(n)) =log |Q(n)|,log log |Q(n)|σQ (n) =log |Q(n)|,2nпричём из определения следует, что 0 6 σQ (n) 6 1 для всех n.14Глава 1. Асимпотические оценки высокой степени точностиКласс ФАЛ (операторов) Q называется невырожденным в том и только томJ(Q(n))случае, когда J(Q(n)) n + m(n), то есть n+m(n)→ ∞.

Класс ФАЛ Q называетсястрого невырожденным в том и только том случае, когда log |Q(n)| log n. КлассQ называется ненулевым классом ФАЛ, если и только если limn→∞ σQ (n) > 0.Непосредственным применением мощностного метода получения нижних оценок можно установить справедливость следующего утверждения.Утверждение 3.

Если Q — невырожденный класс ФАЛ (операторов), тоИКC (Q(n)) & 1 J(Q(n)). Если Q — строго невырожденLCБ (Q(n)) & ρБ J(Q(n)), L2ный класс ФАЛ, то LK (Q(n)) & J(Q(n)).Следствие. Для всякого ненулевого класса ФАЛ Q выполнены неравенства2nИКC (Q(n)) & 1 σ (n) · log |Q(n)| , LK (Q(n)) & σ (n) 2n .LCQБ (Q(n)) & ρБ σQ (n) n , L2 QnnКласс ФАЛ (операторов) Q называется стандартным относительно функционала сложности L и класса схем UCБ , если выполнено асимптотическое неравенство LC(Q(n)).ρJ(Q(n))+O(n+m(n)).Аналогично вводится определения станББдартного класса операторов относительно других классов схем и функционаловсложности. Отметим, что если Q — невырожденный стандартный класс ФАЛ, тоLCБ (Q(n)) ∼ ρБ J(Q(n)).Приведём пример стандартного класса ФАЛ. Рассмотрим множество P2 (n, t) ={f (x1 , . . . , xn ) | ∀α(ν(α) > t ⇒ f (α) = 0)}.

Его мощность равна, очевидно, 2t .Любой функции t = t(n) > 1 можно поставить в соответствие класс ФАЛ Q, определённый равенствами Q(n) = P2 (n, t(n)).Утверждение 4. Для любой функции t = t(n) соответствующий класс Q(n) =P2 (n, t(n)) является стандартным относительно L и класса UC , то естьLC (Q(n)) . logt t + O(n).Доказательство. Сначала рассмотрим случай, когда t > 2n−1 . Пусть f ∈ P2 (n, t) —произвольная функция. Построим для неё СФЭ Σf по асимптотически наилучшемуметоду синтеза.

На одном из этапов этого метода синтеза функция f разлагаетсяпо БП x00 = (xq+1 , . . . , xn ):_f (x0 , x00 ) =Kσ00 (x00 )fσ00 (x0 ),σ 00 ∈B n−qгде x0 = (x1 , . . . , xq ). Из принадлежности функции f классу P2 (n, t) следует, чтопри ν(σ 00 ) > dt/2q e функция fσ00 (x0 ) тождественно равна нулю, следовательно изсхемы Σf можно удалить подсхемы, реализующие такие подфункции. Получимсхему Σ0f со сложностью L(Σ0f ) . logt t .Теперь рассмотрим случай t 6 2n−1 .

Найдётся число k такое, что 2n−k−1 < t 62n−k . Тогда f (x1 , . . . , xn ) = x1 · . . . · xk · f 0 (xk+1 , . . . , xn ). Функция f 0 принадлежитклассу P2 (n − k, t0 ), где t0 > 2n−k−1 , и для неё уже можно применить рассужденияиз предыдущего случая. Получим L(Σf ) 6 L(Σf 0 ) + O(n) . logt t + O(n).§4. Специальные классы функций15Следствие. Если logt t n, то Q(n) = P2 (n, t(n)) — стандартный невырожденный класс ФАЛ, и выполнено асимптотическое равенство LC (Q(n)) ∼ logt t .Замечание. Аналогично доказывается стандартность класса Q(n) = P2 (n, t(n)) отИКC , UК . Ананосительно функционала “обычной” сложности и классов схем UCБ, Uлогичные утверждения справедливы и для классов операторов вида (P2 (n, t(n)))m .Рассмотрим теперь следующие операции над ФАЛ:1. Добавление и изъятие фиктивных БП (переход к равной ФАЛ).2.

Переименование БП без отождествления (переход к конгруэнтной ФАЛ).3. Подстановка констант 0, 1 вместо БП (переход к подфункции).Множество Q ⊆ P2 называется инвариантным классом ФАЛ, если оно замкнутоотносительно трёх указанных операций. Если функция g получена из функции fприменением операций 1–3, то говорят, что g является квазиподфункцией f , а fявляется квазинадфункцией g. Для множества функций F через F e и Fc будемобозначать множества всех квазинадфункций и квазиподфункций для функций изF соответственно.Множества {0}, {1}, {0, 1} называются тривиальными инвариантными классами.

Если инвариантный класс Q не является тривиальным, то Q ⊇ {0, 1}, поскольку Q содержит неконстантую функцию, из которой при помощи операции 3 можнополучить обе константы. Отметим, что если класс Q замкнут по суперпозиции и{0, 1} ⊆ Q, то класс Q является инвариантным. Примерами инвариантных классовмогут, следовательно, служить классы M и L всех монотонных и всех линейныхФАЛ соответственно. При этом класс самодвойственных функций, а также классыT0 , T1 не являются инвариантными (не замкнуты относительно операции 3).

Классвсех симметрических ФАЛ не замкнут относительно операции 1, поэтому такжене является инвариантным. При этом инвариантным является класс Ŝ квазисимметрических ФАЛ, т. е. функций, симметрических по всем своим существеннымпеременным.Утверждение 5. Пусть Q — инвариантный класс ФАЛ. Тогда существует пределlog |Q(n)|σQ = lim σQ (n) = lim.n→∞n→∞2nПри этом число σQ , называемое характеристикой класса Q, удовлетворяет неравенству 0 6 σQ 6 1.Доказательство. Для каждого n выполнено неравенство 0 6 σQ (n) 6 1, то естьпоследовательность σQ (n) ограничена.

Покажем, что она монотонно невозрастает,16Глава 1. Асимпотические оценки высокой степени точностиоткуда будет следовать её сходимость. В силу инвариантности класса Q, всякуюфункцию f из множества Q(n + 1) можно представить в видеf (x1 , . . . , xn+1 ) = xn+1 f (x1 , . . . , xn , 0) ∨ xn+1 f (x1 , . . . , xn , 1)||{z}{z}∈Q(n)∈Q(n)6 log |Q(n)|Отсюда сразу вытекает неравенство |Q(n + 1)| 6 |Q(n)|2 ⇒ log |Q(n+1)|,2n2n+1что и требовалось.

Неравенство 0 6 σQ 6 1 следует из ограничений 0 6 σQ (n) 61.Инвариантные классы с характеристикой σQ = 0 называются нулевыми. Покажем, что инвариантный класс с характеристикой σQ = 1 есть только один — этокласс P2 . Действительно, если инвариантный класс Q не совпадает с P2 , то длянекоторого m будет выполнено неравенство |Q(m)| < |P2 (m)|, откуда следует, чтоσQ (m) < 1. Но последовательность σQ (m), σQ (m + 1), . . . монотонно невозрастает,а значит для предела σQ будет выполнено неравенство σQ 6 σQ (m) < 1.Найдём значение характеристик инвариантных классов M, L и Ŝ. Имеемn2nlog |M (n)| ∼∼√,dn/2e2πnоткуда σM (n) → 0 и следовательно σM = 0.

Для класса линейных функций имеем |L(n)| = 2n+1 , и значит σL = 0. Всякую функцию из множества Ŝ(n) можнополучить так: сначала выбираем k переменных, по которым функция будет существенной, а затем не более чем 2k+1 способами определяем значение функции накаждом слое куба B k (в пределах одного слоя значение функции одно и то же).Отсюда следует, чтоn Xn|Ŝ(n)| 6· 2k+1 = 2 · 3n ,kk=0и поэтому σS^ = 0.

Таким образом, все три класса M, L, Ŝ являются нулевыми.Существуют и ненулевые инвариантныеклассы, отличные от P2 . Например, множество Q = P2 \ {x1 ∨ x2 }e является инвариантным классом с характеристикой0 < σQ < 1 (упражнение). Выше было установлено, что существует единственныйинвариантный класс с характеристикой 1. Можно доказать, что при при любомσ, 0 6 σ < 1 существует континуум инвариантных классов с характеристикой σ.Докажем это в частном случае σ = 0:Утверждение 6. Существует континуум различных инвариантных классов схарактеристикой 0.Доказательство. Отметим, что число различных инвариантных классов не можетбыть больше континуума, поскольку множество P2 счётно.§4.