Изменения

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

[[Файл:XorNotInAC0StepByStepПусть после <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>-ДНФ.gif|404px|thumb|Воспользуемся леммой. Пусть <tex>s = k_{i+1}</tex>, <tex>n = x</tex>, а в качестве <tex>t</tex> возьмем <tex>x - \frac{x}{\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>n_i = n_0^{1/2^i}</tex> при таком выборе <tex>t</tex>. Тогда при достаточно больших <tex>n</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> элементов.]]

Покажем, что после [[Файл:XorNotInAC0StepByStep.gif|404px|thumb|center|Переход от <tex>i+1</tex>-ого шага глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне будет <tex>k_i</tex>. В самом деле, пусть нижний уровень схемы состоит из <tex>\land</tex> элементов, тогда уровень выше <tex>-</tex> из элементов <tex>\lor</tex>. Каждый <tex>\lor</tex> элемент можно считать <tex>k_i</tex>-ДНФ. Отсюда по лемме получаем, что с вероятностью <tex>1-\leftк (\frac{k_i^{10}}{n^{1/2^{i+1}}}\right) ^ {k_{i+1}/2}</tex> функцию можно записать в виде <tex>k_{i+1}</tex>)-КНФ. При достаточно больших <tex>n</tex> это можно сделать с вероятность хотя бы <tex>1-\frac{1}{10n^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементовму шагу.]]

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