Изменения

Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит, степень Степень входа элементов каждого элемента схемы <tex>C_n</tex> — это полином не превосходит полинома от <tex>n</tex>, поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух 2 следующим образом: <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> элементов, а изначально потому, поскольку изначальный размер схемы был полиномиальным и каждый ее элемент мы заменили на полином полиномиальным числом элементов, то после всех замен размер схемы остался останется полиномиальным.

'''Следствие:''' <tex>\mathrm{NC} = \mathrm{AC}</tex><br/>.