Изменения

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

Рассмотрим произвольную схему Допустим, что схема из [[Классы 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> можно подобрать значения части входов так, чтобы значение функции было постоянным,