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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 58 промежуточных версий 6 участников)
Строка 1: Строка 1:
===Hastad’s switching lemma===
+
{{В разработке}}
{{Лемма
 
|statement=
 
Пусть <tex>f</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно, что <tex>Pr[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.</tex>
 
|proof=
 
}}
 
Заметим, что для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
 
 
 
===Теорема===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 13: Строка 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\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> схемой полиномиального размера и постоянной глубиной?
 +
 +
===Теорема===
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
 
<tex>\oplus \notin \mathrm{AC^0}</tex>.
 
<tex>\oplus \notin \mathrm{AC^0}</tex>.
 
|proof=
 
|proof=
Рассмотрим произвольную схему из <tex>\mathrm{AC^0}</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>1</tex>.
 
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет <tex>2n</tex> входных провода, причем последние <tex>n</tex> из них являются отрицанием первых <tex>n</tex> входов.
+
# Схема не содержит элементов <tex>\neg</tex>. В самом деле, вместо схемы с элементами <tex>\neg</tex> можно рассмотреть эквивалентную ей схему из класса <tex>\mathrm{AC^0}</tex> с удвоенным числом входов, причем значения, подаваемые на добавленные входы будут противоположны значениям, подаваемым на исходные входы схемы.
 
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
 
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
# Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.
+
# Все входы лежат на одном уровне. Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.
  
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью на <tex>1</tex> уменьшить глубину схемы, сохранив при этом число входов. Пусть <tex>n~-</tex> длина входной цепочки, а <tex>d~-</tex> глубина схемы. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n^b</tex> было не меньше, чем число элементов в схеме. На каждом шаге случайным образом будем назначать все большее число переменных. Обозначим <tex>n_i~-</tex> число неназначенных переменных на <tex>i</tex>-ом шаге. Тогда на <tex>i + 1</tex>-ом шаге число назначенных переменных будет <tex>n_i - \sqrt{n_i}</tex>. Возьмем <tex>k_i=10b2^i.</tex>
+
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на <tex>1</tex>. Пусть <tex>d~-</tex> глубина схемы, а <tex>n_0~-</tex> число входов схемы. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n_0^b</tex> было не меньше, чем число элементов в схеме. Обозначим <tex>n_i~-</tex> число входов схемы после <tex>i</tex>-го шага. Возьмем <tex>k_i=10b\cdot2^i.</tex>
  
[[Файл:beforeHastadSwitchingTransformation.png|600px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]
+
[[Файл:beforeHastadSwitchingTransformation.png|600x250px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]
  
Покажем, что после <tex>i+1</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>1-\left(\frac{k_i^{10}}{n^{1/2^{i+1}}}\right) ^ {k_{i+1}/2}</tex> функцию можно записать в виде <tex>k_{i+1}</tex>-КНФ. При достаточно больших <tex>n</tex> это можно сделать с вероятность хотя бы <tex>1-\frac{1}{10n^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементов.
+
Докажем по индукции, что после <tex>i</tex>-ого шага с достаточно большой вероятностью глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>.
  
[[Файл:afterHastadSwitchingTransformation.png|600px|thumb|center|Схема на <tex>i+1</tex>-ом шаге.]]
+
1. База индукции верна. Глубина исходной схемы равна <tex>d</tex>, а входная степень каждого элемента равна <tex>1</tex>, что меньше <tex>k_0 = 10b.</tex>
  
Заметим, что лемма применяется не более, чем к <tex>n^b</tex> элементам исходной схемы. Тогда с вероятностью <tex>9/10</tex> после <tex>d-2</tex>-ого шага получаем схему глубины <tex>2</tex>, у которой максимальная степень входа на нижнем уровне не больше <tex>k_{d-2}</tex>. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать <tex>k_{d-2}</tex> переменных. Однако функцию <tex>\oplus</tex> невозможно сделать постоянной, зафиксировав менее <tex>n</tex> переменных. Получили противоречие. Поскольку рассматривали произвольную схему из класса <tex>\mathrm{AC^0}</tex>, верно что <tex>\oplus \notin \mathrm{AC^0}.</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=
 +
Пусть функция <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> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
 +
</div>
 +
Пусть <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|Схема после применения леммы.]]
 +
 +
Заметим, что лемма применяется не более, чем к <tex>n_0^b</tex> элементам исходной схемы. Тогда с вероятностью не менее <tex>1 - \frac{n_0^b}{10n_0^b} = \frac{9}{10}</tex> после (<tex>d-2</tex>)-ого шага получаем схему глубины <tex>2</tex>, у которой максимальная степень входа на нижнем уровне не больше <tex>k_{d-2}</tex>. По построению эта формула либо <tex>k_{d - 2}</tex>-КНФ, либо <tex>k_{d - 2}</tex>-ДНФ.
 +
}}
 +
 +
===Источники===
 +
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]
 +
 +
[[Категория: Теория сложности]]

Текущая версия на 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]

Источники