31
правка
Изменения
→Теоремы
Это очевидно из определения <tex>NC^i</tex> и <tex>AC^i</tex>. <br/>
*<tex>AC^i \subset NC^{i+1}</tex> <br/>
Пусть <tex>L \in AC^i</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Значит степень входа у элементов схемы <tex>C_n</tex> это полином <tex>r(n)</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом:<br/>[[Файл:circuit.jpg]]
При замене каждого такого элемента размер схемы будет оставаться полиномиальным, а глубина увеличится на <tex>log_2 r(n) = O(log(n))</tex>.
}}
