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

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]\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]\oplus[/math]. В силу особенности языка [math]\oplus[/math], распознающая его схема должна зависить от всех своих входов. Однако воспользовавшись леммой, можно с большой вероятностью представить эту схему в виде КНФ или ДНФ. Заметим, что значение КНФ или ДНФ можно сделать постоянным, зафиксировав значение лишь одного дизъюнкта или конъюнкта соответственно. А значит, с высокой вероятностью произвольная схема из класса [math]\mathrm{AC^0}[/math] не распознает язык [math]\oplus[/math], поскольку зависит не от всех входных значений. Покажем, как представить схему из класса [math]\mathrm{AC^0}[/math] в виде КНФ или ДНФ. Не умаляя общности, будем считать, что: Выходная степень каждого элемента равна [math]1[/math]. Схема не содержит элементов [math]\neg[/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]. База индукции верна. Для исходной схемы верно, что её глубина равна [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]\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