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

Hastad’s switching lemma

Лемма:

Пусть функция [math]f[/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]\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_0~-[/math] длина входной цепочки, а [math]d~-[/math] глубина схемы. Выберем минимальное целое [math]b[/math] так, чтобы [math]n^b[/math] было не меньше, чем число элементов в схеме. Обозначим [math]n_i~-[/math] число входов схемы после [math]i[/math]-го шаге. Возьмем [math]k_i=10b\cdot2^i.[/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 = x[/math], а в качестве [math]t[/math] возьмем [math]x - \frac{x}{\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]n_i = n_0^{1/2^i}[/math] при таком выборе [math]t[/math]. Тогда при достаточно больших [math]n[/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]i[/math]-ого к ([math]i+1[/math])-му шагу. Заметим, что лемма применяется не более, чем к [math]n_0^b[/math] элементам исходной схемы. Тогда с вероятностью не менее [math]1 - \frac{n_0^b}{10n_0^b} = 9/10[/math] после ([math]d-2[/math])-ого шага получаем схему глубины [math]2[/math], у которой максимальная степень входа на нижнем уровне не больше [math]k_{d-2}[/math]. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать [math]k_{d-2}[/math] переменных. Однако функцию, распознающую [math]\oplus,[/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