Изменения

Это очевидно понятно из определения <tex>NC^i</tex> и <tex>AC^i</tex>. <br/>

Пусть <tex>L \in AC^i</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит , степень входа элементов схемы <tex>C_n</tex> это полином от <tex>n</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом: <br/>

При замене каждого такого элемента глубина схемы увеличивается не более чем на в <tex>log_2 r(n) = O(log(n))</tex>, а так как изначально глубина схемы была <tex>O(log^i(n))</tex>, то после замены всех элементов глубина схемы станет <tex>O(log^i(n)) \cdot O(log(n)) = O(log^{i+1}(n))</tex>.<br> Так как при замене элемента мы добавляем не более <tex>r(n)</tex> элементов, а так как изначально размер схемы был полиномиальным и каждый ее элемент мы заменили на полином элементов, то после всех замен размер схемы остается остался полиномиальным.