Теорема о непринадлежности 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\limits^{t}_{i=1} {P\left[ A_i(x) = 1 \right]} \le t\cdot2^{-n}[/math]. Поскольку [math]P\left[x \in \oplus\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]\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]-ом шаге. Докажем по индукции, что после [math]i[/math]-ого шага с достаточно большой вероятностью глубина схемы будет [math]d - i[/math], причем наибольшая степень входа элемента на нижнем уровне не будет превосходить [math]k_i[/math]. 1. База индукции верна. Глубина исходной схемы равна [math]d[/math], а входная степень каждого элемента равна [math]1[/math], что меньше [math]k_0 = 10b.[/math] 2. Индукционный переход. Допустим, что после [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]-ДНФ. Воспользуемся следующей леммой: Лемма (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]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