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]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]\triangleleft[/math] |
Источники
