Теорема о непринадлежности XOR классу AC⁰ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Hastad’s switching lemma)
(Теорема)
Строка 22: Строка 22:
 
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
 
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
 
# Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.
 
# Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.
# Листья лежат на одном уровне, причем глубина схемы минимально возможная.
 
  
 
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на <tex>1</tex>, сохранив при этом число входов. Пусть <tex>n_0~-</tex> длина входной цепочки, а <tex>d~-</tex> глубина схемы. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n^b</tex> было не меньше, чем число элементов в схеме. Обозначим <tex>n_i~-</tex> число входов схемы после <tex>i</tex>-го шаге. Возьмем <tex>k_i=10b\cdot2^i.</tex>
 
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на <tex>1</tex>, сохранив при этом число входов. Пусть <tex>n_0~-</tex> длина входной цепочки, а <tex>d~-</tex> глубина схемы. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n^b</tex> было не меньше, чем число элементов в схеме. Обозначим <tex>n_i~-</tex> число входов схемы после <tex>i</tex>-го шаге. Возьмем <tex>k_i=10b\cdot2^i.</tex>
  
Пусть после <tex>i</tex>-ого шага глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне будет <tex>k_i</tex>. В самом деле, пусть нижний уровень схемы состоит из <tex>\land</tex> элементов, тогда уровень выше <tex>-</tex> из элементов <tex>\lor</tex>. Каждый <tex>\lor</tex> элемент можно считать <tex>k_i</tex>-ДНФ. Воспользуемся леммой. Пусть <tex>s = k_{i+1}</tex>, <tex>n = x</tex>, а в качестве <tex>t</tex> возьмем <tex>x - \frac{x}{\sqrt{n_i}}</tex>. Получаем, что с вероятностью <tex>\left(\frac{k_i^{10}}{\sqrt{n_i}}\right) ^ {k_{i+1}/2}</tex> функцию нельзя представить в виде <tex>k_{i+1}</tex>-КНФ. Заметим, что <tex>n_i = n_0^{1/2^i}</tex> при таком выборе <tex>t</tex>. Тогда при достаточно больших <tex>n</tex> верно, что <tex>\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}</tex>. В итоге получаем, что <tex>k_i</tex>-ДНФ можно переписать в виде <tex>k_{i+1}</tex>-КНФ с вероятностью не менее <tex>1 - \frac{1}{10n_0^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементов.
+
Пусть после <tex>i</tex>-ого шага глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне будет <tex>k_i</tex>. Если нижний уровень схемы состоит из <tex>\land</tex> элементов, тогда уровень выше <tex>-</tex> из элементов <tex>\lor</tex>. Каждый <tex>\lor</tex> элемент можно считать <tex>k_i</tex>-ДНФ. Воспользуемся леммой. Пусть <tex>s = k_{i+1}</tex>, <tex>n = x</tex>, а в качестве <tex>t</tex> возьмем <tex>x - \frac{x}{\sqrt{n_i}}</tex>. Получаем, что с вероятностью <tex>\left(\frac{k_i^{10}}{\sqrt{n_i}}\right) ^ {k_{i+1}/2}</tex> функцию нельзя представить в виде <tex>k_{i+1}</tex>-КНФ. Заметим, что <tex>n_i = n_0^{1/2^i}</tex> при таком выборе <tex>t</tex>. Тогда при достаточно больших <tex>n</tex> верно, что <tex>\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}</tex>. В итоге получаем, что <tex>k_i</tex>-ДНФ можно переписать в виде <tex>k_{i+1}</tex>-КНФ с вероятностью не менее <tex>1 - \frac{1}{10n_0^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементов.
  
 
[[Файл:XorNotInAC0StepByStep.gif|404px|thumb|center|Переход от <tex>i</tex>-ого к (<tex>i+1</tex>)-му шагу.]]
 
[[Файл:XorNotInAC0StepByStep.gif|404px|thumb|center|Переход от <tex>i</tex>-ого к (<tex>i+1</tex>)-му шагу.]]

Версия 16:20, 3 июня 2012

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

  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_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]n_0^b[/math] элементам исходной схемы. Тогда с вероятностью не менее [math]1 - \frac{n_0^b}{10n_0^b} = 9/10[/math] после ([math]d-2[/math])-ого шага получаем схему глубины [math]2[/math], у которой максимальная степень входа на нижнем уровне не больше [math]k_{d-2}[/math]. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать [math]k_{d-2}[/math] переменных. Однако функцию, распознающую [math]\oplus,[/math] невозможно сделать постоянной, зафиксировав не все переменные. Получили противоречие. Поскольку рассматривали произвольную схему из класса [math]\mathrm{AC^0}[/math], верно что [math]\oplus \notin \mathrm{AC^0}.[/math]
[math]\triangleleft[/math]

Источники