Основная идея
Допустим, что схема из класса [math]\mathrm{AC^0}[/math] распознает язык [math]\oplus[/math]. Оказывается с высокой вероятностью схему из класса [math]\mathrm{AC^0}[/math] можно представить в виде [math]k[/math]-КНФ или [math]k[/math]-ДНФ, причем [math]k[/math] не зависит от числа входов схемы. Для этого строится итеративный процесс, на каждом шаге которого некоторые случайно выбранные входные значения заменяются на случайные значения. Поскольку степень входа не ограничена, то рассмотрим содержательный случай, когда [math]k[/math] меньше числа входов схемы. Если с вероятностью [math]\frac{1}{2}[/math] входу полученной схемы назначается значение, то с вероятностью не менее [math]\frac{1}{2^k}[/math] значение схемы будет постоянным. Поскольку эта вероятность больше нуля, то для произвольной схемы из класса [math]\mathrm{AC^0}[/math] можно подобрать значения части входов так, чтобы значение функции было постоянным и не зависит от остальных входных значений, поэтому ни одна схема из этого класса не может распознавать язык [math]\oplus[/math].
Технические подробности
Покажем, как представить схему из класса [math]\mathrm{AC^0}[/math] в виде [math]k[/math]-КНФ или [math]k[/math]-ДНФ. Не умаляя общности, будем считать, что:
- Выходная степень каждого элемента равна [math]1[/math].
- Схема не содержит элементов [math]\neg[/math]. В самом деле, вместо схемы с элементами [math]\neg[/math] можно рассмотреть эквивалентную ей схему из класса [math]\mathrm{AC^0}[/math] с удвоенным числом входов, причем значения, подаваемые на добавленные входы будут противоположны значениям, подаваемым на исходные входы схемы.
- Элементы [math]\lor[/math] и [math]\land[/math] чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
- Все входы лежат на одном уровне. Нижний уровень схемы состоит из [math]\land[/math] элементов с единичной степенью входа.
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на [math]1[/math]. Пусть [math]d~-[/math] глубина схемы, а [math]n_0~-[/math] число входов схемы. Выберем минимальное целое [math]b[/math] так, чтобы [math]n_0^b[/math] было не меньше, чем число элементов в схеме. Обозначим [math]n_i~-[/math] число входов схемы после [math]i[/math]-го шага. Возьмем [math]k_i=10b\cdot2^i.[/math]
 Схема на [math]i[/math]-ом шаге. Hastad’s switching lemma
| Лемма: |
Пусть функция [math]f(x_1, ...,x_n)[/math] представима в виде [math]k[/math]- ДНФ, а [math]p~-[/math] случайное назначение [math]t[/math] случайно выбранным аргументам случайных значений. Тогда при [math]s \ge 2[/math] верно, что: [math]P[f|_p[/math] не представима в виде [math]s[/math]- КНФ[math]]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}[/math], где [math]f|_p[/math] получено при подстановке в функцию [math]f[/math] значений из [math]p[/math]. |
Замечание. Для функции [math]\overline{f}[/math] можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
Докажем по индукции, что после [math]i[/math]-ого шага с достаточно большой вероятностью глубина схемы будет [math]d - i[/math], причем наибольшая степень входа элемента на нижнем уровне не будет превосходить [math]k_i[/math].
- База индукции верна. Глубина исходной схемы равна [math]d[/math], а входная степень каждого элемента равна [math]1[/math], что меньше [math]k_0 = 10b.[/math]
- Индукционный переход. Допустим, что после [math]i[/math]-ого шага глубина схемы будет [math]d - i[/math], причем наибольшая степень входа элемента на нижнем уровне не будет превосходить [math]k_i[/math]. Если нижний уровень схемы состоит из [math]\land[/math] элементов, тогда уровень выше [math]-[/math] из элементов [math]\lor[/math]. Каждый [math]\lor[/math] элемент можно считать [math]k_i[/math]-ДНФ. Воспользуемся леммой. Пусть [math]s = k_{i+1}[/math], [math]n~-[/math] число входов схемы, соответствующих рассматриваемому элементу [math]\lor[/math]. Тогда в качестве [math]t[/math] возьмем [math]n - \frac{n}{\sqrt{n_i}}[/math]. Значит, с вероятностью не менее [math]\left(\frac{k_i^{10}}{\sqrt{n_i}}\right) ^ {k_{i+1}/2}[/math] функцию нельзя представить в виде [math]k_{i+1}[/math]-КНФ. Поскольку [math]t[/math] выбиралось таким образом, то при переходе к следующему шагу число входов схемы уменьшилось в [math]\sqrt{n_i}[/math] раз, поэтому [math]n_i = n_0^{1/2^i}.[/math] Тогда при достаточно больших [math]n_0[/math] верно, что [math]\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}[/math]. В итоге получаем, что [math]k_i[/math]-ДНФ можно переписать в виде [math]k_{i+1}[/math]-КНФ с вероятностью не менее [math]1 - \frac{1}{10n_0^b}[/math]. Поскольку верхний уровень КНФ состоит из [math]\land[/math] элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на [math]1[/math]. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из [math]\lor[/math] элементов.
 Схема после применения леммы. |
