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

Лемма:

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