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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
===Hastad’s switching lemma===
 
{{Лемма
 
|statement=
 
Пусть функция <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=
 
}}
 
'''Замечание.''' Для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
 
 
===Теорема===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 14: Строка 5:
 
}}
 
}}
  
 +
===Теорема===
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Строка 30: Строка 22:
  
 
[[Файл:beforeHastadSwitchingTransformation.png|600x250px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]
 
[[Файл:beforeHastadSwitchingTransformation.png|600x250px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]
 +
 +
===Hastad’s switching lemma===
 +
{{Лемма
 +
|statement=
 +
Пусть функция <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=
 +
}}
 +
'''Замечание.''' Для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
  
 
Докажем по индукции, что после <tex>i</tex>-ого шага с достаточно большой вероятностью глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>.
 
Докажем по индукции, что после <tex>i</tex>-ого шага с достаточно большой вероятностью глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>.

Версия 11:37, 27 июня 2012

Эта статья находится в разработке!
Определение:
[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]\oplus[/math]. В силу особенности языка [math]\oplus[/math], распознающая его схема должна зависить от значений всех своих входов. Однако воспользовавшись леммой, можно с вероятностью, отличной от нуля, представить эту схему в виде [math]k[/math]-КНФ или [math]k[/math]-ДНФ, причем [math]k[/math] не зависит от числа входов схемы. Поскольку рассматриваем схему из класса [math]\mathrm{AC^0}[/math], то по определению степень входа не ограничена. Рассмотрим содержательный случай, когда [math]k[/math] меньше числа входов схемы. Заметим, что значение [math]k[/math]-КНФ или [math]k[/math]-ДНФ можно сделать постоянным, зафиксировав значение не более, чем [math]k[/math] входов. Для этого достаточно зафиксировать значение лишь одного дизъюнкта или конъюнкта соответственно. Если с вероятностью [math]\frac{1}{2}[/math] входу полученной схемы назначается значение, то с вероятностью не менее [math]\frac{1}{2^k}[/math] значение схемы будет постоянным. Поскольку эта вероятность больше нуля, то для произвольной схемы из класса [math]\mathrm{AC^0}[/math] можно подобрать значения части входов так, чтобы значение функции было постоянным, поэтому ни одна схема из этого класса не может распознавать язык [math]\oplus[/math].

Покажем, как представить схему из класса [math]\mathrm{AC^0}[/math] в виде [math]k[/math]-КНФ или [math]k[/math]-ДНФ. Не умаляя общности, будем считать, что:

  1. Выходная степень каждого элемента равна [math]1[/math].
  2. Схема не содержит элементов [math]\neg[/math]. В самом деле, вместо схемы с элементами [math]\neg[/math] можно рассмотреть эквивалентную ей схему из класса [math]\mathrm{AC^0}[/math] с удвоенным числом входов, причем значения, подаваемые на добавленные входы будут противоположны значениям, подаваемым на исходные входы схемы.
  3. Элементы [math]\lor[/math] и [math]\land[/math] чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
  4. Все входы лежат на одном уровне. Нижний уровень схемы состоит из [math]\land[/math] элементов с единичной степенью входа.

Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на [math]1[/math]. Пусть [math]d~-[/math] глубина схемы, а [math]n_0~-[/math] число входов схемы. Выберем минимальное целое [math]b[/math] так, чтобы [math]n_0^b[/math] было не меньше, чем число элементов в схеме. Обозначим [math]n_i~-[/math] число входов схемы после [math]i[/math]-го шага. Возьмем [math]k_i=10b\cdot2^i.[/math]

Схема на [math]i[/math]-ом шаге.

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]i[/math]-ого шага с достаточно большой вероятностью глубина схемы будет [math]d - i[/math], причем наибольшая степень входа элемента на нижнем уровне не будет превосходить [math]k_i[/math].

  • База индукции верна. Глубина исходной схемы равна [math]d[/math], а входная степень каждого элемента равна [math]1[/math], что меньше [math]k_0 = 10b.[/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~-[/math] число входов схемы, соответствующих рассматриваемому элементу [math]\lor[/math]. Тогда в качестве [math]t[/math] возьмем [math]n - \frac{n}{\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]t[/math] выбиралось таким образом, то при переходе к следующему шагу число входов схемы уменьшилось в [math]\sqrt{n_i}[/math] раз, поэтому [math]n_i = n_0^{1/2^i}.[/math] Тогда при достаточно больших [math]n_0[/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]n_0^b[/math] элементам исходной схемы. Тогда с вероятностью не менее [math]1 - \frac{n_0^b}{10n_0^b} = \frac{9}{10}[/math] после ([math]d-2[/math])-ого шага получаем схему глубины [math]2[/math], у которой максимальная степень входа на нижнем уровне не больше [math]k_{d-2}[/math]. По построению эта формула либо [math]k_{d - 2}[/math]-КНФ, либо [math]k_{d - 2}[/math]-ДНФ.
[math]\triangleleft[/math]

Источники