Изменения

===Hastad’s switching lemma==={{Лемма|statement=Пусть функция <tex>f(x_1, ...,x_n)</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайное назначение <tex>t</tex> случайно выбранным аргументам случайных значений. Тогда при <tex>s \ge 2</tex> верно, что: <br><tex>P[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2В разработке}</tex>, где <tex>f|_p</tex> получено при подстановке в функцию <tex>f</tex> значений из <tex>p</tex>.|proof=}}'''Замечание.''' Для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот. ===Теорема===

Рассмотрим произвольную схему ===Основная идея===Допустим, что схема из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex>распознает язык <tex>\oplus</tex>. Оказывается, что с высокой вероятностью схему из класса <tex>\mathrm{AC^0}</tex> можно представить в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ, причем <tex>k</tex> не зависит от числа входов схемы. Для этого строится [[Теорема о непринадлежности XOR классу AC⁰#Технические подробности|итеративный процесс]], на каждом шаге которого некоторые случайно выбранные входные значения заменяются случайными. Поскольку степень входа не ограничена, то рассмотрим содержательный случай, когда <tex>k</tex> меньше числа входов схемы. Если с вероятностью <tex>\frac{1}{2}</tex> входу полученной схемы назначается значение, то с вероятностью не менее <tex>\frac{1}{2^k}</tex> значение схемы будет постоянным. Поскольку эта вероятность больше нуля, то для произвольной схемы из класса <tex>\mathrm{AC^0}</tex> можно подобрать значения части входов так, чтобы значение функции было постоянным и не зависит от остальных входных значений, поэтому ни одна схема из этого класса не может распознавать язык <tex>\oplus</tex>. ===Технические подробности===Покажем, как представить схему из класса <tex>\mathrm{AC^0}</tex> в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ. Не умаляя общности, будем считать, что:

# Схема имеет не содержит элементов <tex>2n_0\neg</tex> входных провода. В самом деле, причем последние вместо схемы с элементами <tex>n_0\neg</tex> можно рассмотреть эквивалентную ей схему из них являются отрицанием первых класса <tex>n_0\mathrm{AC^0}</tex> с удвоенным числом входов, причем значения, подаваемые на добавленные входы будут противоположны значениям, подаваемым на исходные входы схемы.

# Все входы лежат на одном уровне. Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.

Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на <tex>1</tex>, сохранив при этом число входов. Пусть <tex>d~-</tex> глубина схемы, а <tex>n_0~-</tex> число входов схемы. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n_0^b</tex> было не меньше, чем число элементов в схеме. Обозначим <tex>n_i~-</tex> число входов схемы после <tex>i</tex>-го шага. Возьмем <tex>k_i=10b\cdot2^i.</tex>

Пусть Докажем по индукции, что после <tex>i</tex>-ого шага с достаточно большой вероятностью глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>. 1. База индукции верна. Глубина исходной схемы равна <tex>d</tex>, а входная степень каждого элемента равна <tex>1</tex>, что меньше <tex>k_0 = 10b.</tex> 2. Индукционный переход. Допустим, что после <tex>i</tex>-ого шага глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>. Если нижний уровень схемы состоит из <tex>\land</tex> элементов, тогда уровень выше <tex>-</tex> из элементов <tex>\lor</tex>. Каждый <tex>\lor</tex> элемент можно считать <tex>k_i</tex>-ДНФ. Воспользуемся следующей леммой:<div style="border:1px solid #00A; padding: 4px; padding-left: 10px; margin: 10px;">{{Лемма|about=Hastad’s switching lemma|statement=Пусть функция <tex>f(x_1, ...,x_n)</tex> представима в виде <tex>k</tex>-ДНФ, а <tex>p~-</tex> случайное назначение <tex>t</tex> случайно выбранным аргументам случайных значений. Тогда при <tex>s \ge 2</tex> верно, что: <br><tex>P[f|_p</tex> не представима в виде <tex>s</tex>-КНФ<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}</tex>, где <tex>f|_p</tex> получено при подстановке в функцию <tex>f</tex> значений из <tex>p</tex>.|proof=}}'''Замечание.''' Для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.</div>Пусть <tex>s = k_{i+1}</tex>, <tex>n~-</tex> число входов схемы, соответствующих рассматриваемому элементу <tex>\lor</tex>. Тогда в качестве <tex>t</tex> возьмем <tex>n - \frac{n}{\sqrt{n_i}}</tex>. Значит, с вероятностью не менее <tex>\left(\frac{k_i^{10}}{\sqrt{n_i}}\right) ^ {k_{i+1}/2}</tex> функцию нельзя представить в виде <tex>k_{i+1}</tex>-КНФ. ЗаметимПоскольку <tex>t</tex> выбиралось таким образом, что то при переходе к следующему шагу число входов схемы уменьшилось в <tex>\sqrt{n_i}</tex> раз, поэтому <tex>n_i = n_0^{1/2^i}.</tex> при таком выборе <tex>t</tex>. Тогда при достаточно больших <tex>n_0</tex> верно, что <tex>\left(\frac{k_i^{10}}{\sqrt{n_i}}\right) ^ {k_{i+1}/2} = \left(\frac{k_i^{10}}{n_0^{1/2^{i+1}}}\right) ^ {k_{i+1}/2} \le \frac{1}{10n_0^b}</tex>. В итоге получаем, что <tex>k_i</tex>-ДНФ можно переписать в виде <tex>k_{i+1}</tex>-КНФ с вероятностью не менее <tex>1 - \frac{1}{10n_0^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементов.

Заметим, что лемма применяется не более, чем к <tex>n_0^b</tex> элементам исходной схемы. Тогда с вероятностью не менее <tex>1 - \frac{n_0^b}{10n_0^b} = \frac{9}{10}</tex> после (<tex>d-2</tex>)-ого шага получаем схему глубины <tex>2</tex>, у которой максимальная степень входа на нижнем уровне не больше <tex>k_{d-2}</tex>. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать <tex>k_{d-2}</tex> переменных. Однако функцию-КНФ, распознающую либо <tex>\oplus,</tex> невозможно сделать постоянной, зафиксировав не все переменные. Получили противоречие. Поскольку рассматривали произвольную схему из класса <tex>\mathrmk_{AC^0d - 2}</tex>, верно что <tex>\oplus \notin \mathrm{AC^0}-ДНФ.</tex>