Материал из Викиконспекты
| Лемма: |
Пусть [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]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]\triangleleft[/math] |
