Теорема о непринадлежности 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]. Не умаляя общности, будем считать, что:

  1. Выходная степень каждого элемента равна [math]1[/math].
  2. Схема имеет [math]2n[/math] входных провода, причем последние [math]n[/math] из них являются отрицанием первых [math]n[/math] входов.
  3. Элементы [math]\lor[/math] и [math]\land[/math] чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
  4. Нижний уровень схемы состоит из [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]