Теорема о непринадлежности XOR классу AC⁰

Теорема

Определение:

$\oplus~-$ язык над алфавитом $\left\{0, 1\right\}$, состоящий из слов, содержащих нечетное число $1.$

Теорема:

$\oplus \notin \mathrm{AC^0}$.

Доказательство:

$\triangleright$

Рассмотрим произвольную схему из $\mathrm{AC^0}$. Не умаляя общности, будем считать, что: Выходная степень каждого элемента равна $1$. Схема имеет $2n$ входных провода, причем последние $n$ из них являются отрицанием первых $n$ входов. Элементы $\lor$ и $\land$ чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми. Нижний уровень схемы состоит из $\land$ элементов с единичной степенью входа. Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью на $1$ уменьшить глубину схемы, сохранив при этом число входов. Пусть $n~-$ длина входной цепочки, а $d~-$ глубина схемы. Выберем минимальное целое $b$ так, чтобы $n^b$ было не меньше, чем число элементов в схеме. На каждом шаге случайным образом будем назначать все большее число переменных. Обозначим $n_i~-$ число неназначенных переменных на $i$-ом шаге. Тогда на $i + 1$-ом шаге число назначенных переменных будет $n_i - \sqrt{n_i}$. Возьмем $k_i=10b2^i.$ Схема на $i$-ом шаге. Покажем, что после $i+1$-ого шага глубина схемы будет $d - i$, причем наибольшая степень входа элемента на нижнем уровне будет $k_i$. В самом деле, пусть нижний уровень схемы состоит из $\land$ элементов, тогда уровень выше $-$ из элементов $\lor$. Каждый $\lor$ элемент можно считать $k_i$-ДНФ. Отсюда по лемме получаем, что с вероятностью $1-\left(\frac{k_i^{10}}{n^{1/2^{i+1}}}\right) ^ {k_{i+1}/2}$ функцию можно записать в виде $k_{i+1}$-КНФ. При достаточно больших $n$ это можно сделать с вероятность хотя бы $1-\frac{1}{10n^b}$. Поскольку верхний уровень КНФ состоит из $\land$ элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на $1$. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из $\lor$ элементов. Схема на $i+1$-ом шаге. Заметим, что лемма применяется не более, чем к $n^b$ элементам исходной схемы. Тогда с вероятностью $9/10$ после $d-2$-ого шага получаем схему глубины $2$, у которой максимальная степень входа на нижнем уровне не больше $k_{d-2}$. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать $k_{d-2}$ переменных. Однако функцию $\oplus$ невозможно сделать постоянной, зафиксировав менее $n$ переменных. Получили противоречие. Поскольку рассматривали произвольную схему из класса $\mathrm{AC^0}$, верно что $\oplus \notin \mathrm{AC^0}.$

$\triangleleft$