1632
правки
Изменения
м
rollbackEdits.php mass rollback
}}
Предположим, что [[ДНФ]] <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(x) = 1\right] = \frac{1}{2}</tex>, то <tex>t \ge 2^{n - 1}</tex>. Аналогичный результат можно получить и для [[КНФ]].
Отсюда и возникает вопрос: можно ли распознавать <tex>\oplus</tex> схемой полиномиального размера и постоянной глубиной?
|proof=
===Основная идея===
Допустим, что схема из [[Классы 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>.
===Технические подробности===
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> элементов.
