Изменения

Перейти к: навигация, поиск

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

Нет изменений в размере, 19:56, 2 июня 2012
м
Теорема
# Нижний уровень схемы состоит из <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=10b\cdot2^i.</tex>
[[Файл:beforeHastadSwitchingTransformation.png|600px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]

Навигация