Викиконспекты - Вклад участника [ru]

Теорема о непринадлежности XOR классу AC⁰

2012-05-20T20:00:54Z

91.122.87.140:

===Hastad’s switching lemma===
{{Лемма
|statement=
Пусть <tex>f</tex> представима в виде k-ДНФ, а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно, что <tex>Pr[f|_p</tex> не представима в виде s-КНФ<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.</tex>
|proof=
}}
Заметим, что для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
===Теорема===
{{Теорема
|statement=
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
Рассмотрим произвольную схему из <tex>\mathrm{AC^0}</tex>. Не умаляя общности, будем считать, что:
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет <tex>2n</tex> входных провода, причем последние <tex>n</tex> из них являются отрицанием первых <tex>n</tex> входов.
# Элементы <tex>\lor</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>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>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>
}}
===Источники===
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

Теорема о непринадлежности XOR классу AC⁰

2012-05-20T19:35:24Z

91.122.87.140:

{{Лемма
|statement=
Пусть <tex>f</tex> представима в виде k-ДНФ, а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно, что <tex>Pr[f|_p</tex> не представима в виде s-КНФ<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}</tex>.
|proof=
}}
{{Теорема
|statement=
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
Рассмотрим произвольную схему из <tex>\mathrm{AC^0}</tex>. Не умаляя общности, будем считать, что:
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет <tex>2n</tex> входных провода, причем последние <tex>n</tex> из них являются отрицанием первых <tex>n</tex> входов.
# Элементы <tex>\lor</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>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>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>
}}
=Источники=
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

Теорема о непринадлежности XOR классу AC⁰

2012-05-20T18:11:17Z

91.122.87.140:

Теорема о непринадлежности XOR классу AC⁰

2012-05-20T18:07:04Z

91.122.87.140: