Изменения

Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью на <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>.