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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 2 участников)
Строка 5: Строка 5:
 
}}
 
}}
  
Предположим, что [[ДНФ]] <tex>C</tex> распознает язык <tex>\oplus</tex>. Каждый [[ДНФ|конъюнкт]] <tex>C</tex> зависит от всех входных значений. В противном случае допустим, что некоторый конъюнкт <tex>C</tex> не зависит от значения <tex>x_i</tex>. Тогда можно подобрать такие входные значения, при которых значение этого конъюнкта (а значит и <tex>C</tex>) будет равно <tex>1</tex> и не зависить от значения <tex>x_i</tex>. Однако при различных значениях <tex>x_i</tex> значение <tex>C</tex> должно изменяться, так как <tex>C</tex> распознает <tex>\oplus</tex>. Значит, предположение неверно, поэтому каждый конъюнкт <tex>C</tex> зависит от всех входных значений. Предположим, что <tex>C<tex> состоит из конъюнктов <tex>A_1</tex>, ..., <tex>A_t</tex>. Тогда для случайного входа <tex>x \sim \left\{ 0, 1 \right\} ^n</tex> верно, что <tex>P\left[C(x)=1\right] \le \sum^{t}_{i=1} {P\left[ A_i(x) = 1 \right]} \le t\cdot2^{-n}</tex>.
+
Предположим, что [[ДНФ]] <tex>C</tex> распознает язык <tex>\oplus</tex>. Каждый [[ДНФ|конъюнкт]] <tex>C</tex> зависит от всех входных значений. В противном случае допустим, что некоторый конъюнкт <tex>C</tex> не зависит от значения <tex>x_i</tex>. Тогда можно подобрать такие входные значения, при которых значение этого конъюнкта (а значит и <tex>C</tex>) будет равно <tex>1</tex> и не зависить от значения <tex>x_i</tex>. Однако при различных значениях <tex>x_i</tex> значение <tex>C</tex> должно изменяться, так как <tex>C</tex> распознает <tex>\oplus</tex>. Значит, предположение неверно, поэтому каждый конъюнкт <tex>C</tex> зависит от всех входных значений. Пусть <tex>C</tex> состоит из конъюнктов <tex>A_1</tex>, ..., <tex>A_t</tex>. Тогда для случайного входа <tex>x \sim \left\{ 0, 1 \right\} ^n</tex> верно, что <tex>P\left[C(x)=1\right] \le \sum\limits^{t}_{i=1} {P\left[ A_i(x) = 1 \right]} \le t\cdot2^{-n}</tex>. Поскольку <tex>P\left[x \in \oplus\right] = \frac{1}{2}</tex>, то <tex>t \ge 2^{n - 1}</tex>. Аналогичный результат можно получить и для [[КНФ]].
 +
 
 +
Отсюда и возникает вопрос: можно ли распознавать <tex>\oplus</tex> схемой полиномиального размера и постоянной глубиной?
  
 
===Теорема===
 
===Теорема===
Строка 12: Строка 14:
 
<tex>\oplus \notin \mathrm{AC^0}</tex>.
 
<tex>\oplus \notin \mathrm{AC^0}</tex>.
 
|proof=
 
|proof=
Рассмотрим произвольную схему из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex>. Допустим, что эта схема распознает язык <tex>\oplus</tex>. В силу особенности языка <tex>\oplus</tex>, распознающая его схема должна зависить от значений всех своих входов. Однако воспользовавшись леммой, можно с вероятностью, отличной от нуля, представить эту схему в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ, причем <tex>k</tex> не зависит от числа входов схемы. Поскольку рассматриваем схему из класса <tex>\mathrm{AC^0}</tex>, то по определению степень входа не ограничена. Рассмотрим содержательный случай, когда <tex>k</tex>  меньше числа входов схемы. Заметим, что значение <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ можно сделать постоянным, зафиксировав значение не более, чем <tex>k</tex> входов. Для этого достаточно зафиксировать значение лишь одного дизъюнкта или конъюнкта соответственно. Если с вероятностью <tex>\frac{1}{2}</tex> входу полученной схемы назначается значение, то с вероятностью не менее <tex>\frac{1}{2^k}</tex> значение схемы будет постоянным. Поскольку эта вероятность больше нуля, то для произвольной схемы из класса <tex>\mathrm{AC^0}</tex> можно подобрать значения части входов так, чтобы значение функции было постоянным,  
+
===Основная идея===
поэтому ни одна схема из этого класса не может распознавать язык <tex>\oplus</tex>.
+
Допустим, что схема из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex> распознает язык <tex>\oplus</tex>. Оказывается, что с высокой вероятностью схему из класса <tex>\mathrm{AC^0}</tex> можно представить в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ, причем <tex>k</tex> не зависит от числа входов схемы. Для этого строится [[Теорема о непринадлежности XOR классу AC⁰#Технические подробности|итеративный процесс]], на каждом шаге которого некоторые случайно выбранные входные значения заменяются случайными. Поскольку степень входа не ограничена, то рассмотрим содержательный случай, когда <tex>k</tex>  меньше числа входов схемы. Если с вероятностью <tex>\frac{1}{2}</tex> входу полученной схемы назначается значение, то с вероятностью не менее <tex>\frac{1}{2^k}</tex> значение схемы будет постоянным. Поскольку эта вероятность больше нуля, то для произвольной схемы из класса <tex>\mathrm{AC^0}</tex> можно подобрать значения части входов так, чтобы значение функции было постоянным и не зависит от остальных входных значений, поэтому ни одна схема из этого класса не может распознавать язык <tex>\oplus</tex>.
  
 +
===Технические подробности===
 
Покажем, как представить схему из класса <tex>\mathrm{AC^0}</tex> в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ. Не умаляя общности, будем считать, что:
 
Покажем, как представить схему из класса <tex>\mathrm{AC^0}</tex> в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ. Не умаляя общности, будем считать, что:
 
# Выходная степень каждого элемента равна <tex>1</tex>.
 
# Выходная степень каждого элемента равна <tex>1</tex>.
Строка 25: Строка 28:
 
[[Файл:beforeHastadSwitchingTransformation.png|600x250px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]
 
[[Файл:beforeHastadSwitchingTransformation.png|600x250px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]
  
===Hastad’s switching lemma===
+
Докажем по индукции, что после <tex>i</tex>-ого шага с достаточно большой вероятностью глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>.
 +
 
 +
1. База индукции верна. Глубина исходной схемы равна <tex>d</tex>, а входная степень каждого элемента равна <tex>1</tex>, что меньше <tex>k_0 = 10b.</tex>
 +
 
 +
2. Индукционный переход. Допустим, что после <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>-ДНФ. Воспользуемся следующей леммой:
 +
<div style="border:1px solid #00A; padding: 4px; padding-left: 10px; margin: 10px;">
 
{{Лемма
 
{{Лемма
 +
|about=Hastad’s switching lemma
 
|statement=
 
|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>.
+
Пусть функция <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=
 
}}
 
}}
 
'''Замечание.''' Для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
 
'''Замечание.''' Для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
 
+
</div>
Докажем по индукции, что после <tex>i</tex>-ого шага с достаточно большой вероятностью глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>.
+
Пусть <tex>s = k_{i+1}</tex>, <tex>n~-</tex> число входов схемы, соответствующих рассматриваемому элементу <tex>\lor</tex>. Тогда в качестве <tex>t</tex> возьмем <tex>n - \frac{n}{\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>t</tex> выбиралось таким образом, то при переходе к следующему шагу число входов схемы уменьшилось в <tex>\sqrt{n_i}</tex> раз, поэтому <tex>n_i = n_0^{1/2^i}.</tex> Тогда при достаточно больших <tex>n_0</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>d</tex>, а входная степень каждого элемента равна <tex>1</tex>, что меньше <tex>k_0 = 10b.</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~-</tex> число входов схемы, соответствующих рассматриваемому элементу <tex>\lor</tex>. Тогда в качестве <tex>t</tex> возьмем <tex>n - \frac{n}{\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>t</tex> выбиралось таким образом, то при переходе к следующему шагу число входов схемы уменьшилось в <tex>\sqrt{n_i}</tex> раз, поэтому <tex>n_i = n_0^{1/2^i}.</tex> Тогда при достаточно больших <tex>n_0</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> элементов.
 
  
 
[[Файл:afterHastadSwitchingTransformation.png|600x250px|thumb|center|Схема после применения леммы.]]
 
[[Файл:afterHastadSwitchingTransformation.png|600x250px|thumb|center|Схема после применения леммы.]]

Текущая версия на 19:15, 4 сентября 2022

Эта статья находится в разработке!
Определение:
[math]\oplus~-[/math] язык над алфавитом [math]\left\{0, 1\right\}[/math], состоящий из слов, содержащих нечетное число [math]1.[/math]


Предположим, что ДНФ [math]C[/math] распознает язык [math]\oplus[/math]. Каждый конъюнкт [math]C[/math] зависит от всех входных значений. В противном случае допустим, что некоторый конъюнкт [math]C[/math] не зависит от значения [math]x_i[/math]. Тогда можно подобрать такие входные значения, при которых значение этого конъюнкта (а значит и [math]C[/math]) будет равно [math]1[/math] и не зависить от значения [math]x_i[/math]. Однако при различных значениях [math]x_i[/math] значение [math]C[/math] должно изменяться, так как [math]C[/math] распознает [math]\oplus[/math]. Значит, предположение неверно, поэтому каждый конъюнкт [math]C[/math] зависит от всех входных значений. Пусть [math]C[/math] состоит из конъюнктов [math]A_1[/math], ..., [math]A_t[/math]. Тогда для случайного входа [math]x \sim \left\{ 0, 1 \right\} ^n[/math] верно, что [math]P\left[C(x)=1\right] \le \sum\limits^{t}_{i=1} {P\left[ A_i(x) = 1 \right]} \le t\cdot2^{-n}[/math]. Поскольку [math]P\left[x \in \oplus\right] = \frac{1}{2}[/math], то [math]t \ge 2^{n - 1}[/math]. Аналогичный результат можно получить и для КНФ.

Отсюда и возникает вопрос: можно ли распознавать [math]\oplus[/math] схемой полиномиального размера и постоянной глубиной?

Теорема

Теорема:
[math]\oplus \notin \mathrm{AC^0}[/math].
Доказательство:
[math]\triangleright[/math]

Основная идея

Допустим, что схема из класса [math]\mathrm{AC^0}[/math] распознает язык [math]\oplus[/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]-ом шаге.

Докажем по индукции, что после [math]i[/math]-ого шага с достаточно большой вероятностью глубина схемы будет [math]d - i[/math], причем наибольшая степень входа элемента на нижнем уровне не будет превосходить [math]k_i[/math].

1. База индукции верна. Глубина исходной схемы равна [math]d[/math], а входная степень каждого элемента равна [math]1[/math], что меньше [math]k_0 = 10b.[/math]

2. Индукционный переход. Допустим, что после [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]-ДНФ. Воспользуемся следующей леммой:

Лемма (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]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]

Источники