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

Эта статья находится в разработке!

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

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

Предположим, что ДНФ [math]C[/math] распознает язык [math]\oplus[/math]. Каждый конъюнкт [math]C[/math] зависит от всех входных значений. В противном случае допустим, что некоторый конъюнкт [math]C[/math] не зависит от значения [math]x_i[/math]. Тогда можно подобрать такие входные значения, при которых значение этого конъюнкта (а значит и [math]C[/math]) будет равно [math]1[/math] и не зависить от значения [math]x_i[/math]. Однако при различных значениях [math]x_i[/math] значение [math]C[/math] должно изменяться, так как [math]C[/math] распознает [math]\oplus[/math]. Значит, предположение неверно, поэтому каждый конъюнкт [math]C[/math] зависит от всех входных значений. Предположим, что [math]C[/math] состоит из конъюнктов [math]A_1[/math], ..., [math]A_t[/math]. Тогда для случайного входа [math]x \sim \left\{ 0, 1 \right\} ^n[/math] верно, что [math]P\left[C(x)=1\right] \le \sum^{t}_{i=1} {P\left[ A_i(x) = 1 \right]} \le t\cdot2^{-n}[/math]. Поскольку [math]P\left[ \oplus(x) = 1\right] = \frac{1}{2}[/math], то [math]t \ge 2^{n - 1}[/math]. Аналогичный результат можно получить и для КНФ.

Отсюда и возникает вопрос: можно ли распознавать [math]\oplus[/math] схемой полиномиального размера и постоянной глубиной?

Теорема

Теорема:

[math]\oplus \notin \mathrm{AC^0}[/math].

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Источники

• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach