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

Hastad’s switching lemma

Лемма:

Пусть [math]f[/math] представима в виде [math]k[/math]-ДНФ, а [math]p~-[/math] случайная выборка [math]t[/math] случайных бит входа. Тогда при [math]s \ge 2[/math] верно, что [math]Pr[f|_p[/math] не представима в виде [math]s[/math]-КНФ[math]]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.[/math]

Заметим, что для функции [math]\overline{f}[/math] можно получить такой же результат, изменив КНФ на ДНФ и наоборот.

Теорема

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Источники

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