Теорема о непринадлежности XOR классу AC⁰ — различия между версиями
Rost (обсуждение | вклад) |
Rost (обсуждение | вклад) (→Hastad’s switching lemma) |
||
Строка 2: | Строка 2: | ||
{{Лемма | {{Лемма | ||
|statement= | |statement= | ||
− | Пусть функция <tex>f</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайное назначение <tex>t</tex> случайно выбранным аргументам случайно выбранных значений. Тогда при <tex>s \ge 2</tex> верно, что: <br><tex>P[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}</tex>, где <tex>f|_p</tex> получено при подстановки в функцию <tex>f</tex> значений из <tex>p</tex>. | + | Пусть функция <tex>f(x_1, ...,x_n)</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайное назначение <tex>t</tex> случайно выбранным аргументам случайно выбранных значений. Тогда при <tex>s \ge 2</tex> верно, что: <br><tex>P[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}</tex>, где <tex>f|_p</tex> получено при подстановки в функцию <tex>f</tex> значений из <tex>p</tex>. |
|proof= | |proof= | ||
}} | }} |
Версия 16:16, 3 июня 2012
Hastad’s switching lemma
Лемма: |
представима в виде - |
Замечание. Для функции
можно получить такой же результат, изменив КНФ на ДНФ и наоборот.Теорема
Определение: |
язык над алфавитом , состоящий из слов, содержащих нечетное число |
Теорема: |
. |
Доказательство: |
Рассмотрим произвольную схему из класса . Не умаляя общности, будем считать, что:
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на , сохранив при этом число входов. Пусть длина входной цепочки, а глубина схемы. Выберем минимальное целое так, чтобы было не меньше, чем число элементов в схеме. Обозначим число входов схемы после -го шаге. ВозьмемПусть после -ого шага глубина схемы будет , причем наибольшая степень входа элемента на нижнем уровне будет . В самом деле, пусть нижний уровень схемы состоит из элементов, тогда уровень выше из элементов . Каждый элемент можно считать -ДНФ. Воспользуемся леммой. Пусть , , а в качестве возьмем . Получаем, что с вероятностью функцию нельзя представить в виде -КНФ. Заметим, что при таком выборе . Тогда при достаточно больших верно, что . В итоге получаем, что -ДНФ можно переписать в виде -КНФ с вероятностью не менее . Поскольку верхний уровень КНФ состоит из элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на . Аналогично рассматриваем случай, когда нижний уровень схемы состоит из элементов. Заметим, что лемма применяется не более, чем к элементам исходной схемы. Тогда с вероятностью не менее после ( )-ого шага получаем схему глубины , у которой максимальная степень входа на нижнем уровне не больше . По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать переменных. Однако функцию, распознающую невозможно сделать постоянной, зафиксировав не все переменные. Получили противоречие. Поскольку рассматривали произвольную схему из класса , верно что |
Источники
- Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach