Бюрократы, editor, Администраторы
422
правки
Изменения
м
→Теоремы
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. <br/>
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> <br/>
Пусть <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/> [[Файл:AndCircuit.png|700px500px|center]]
При такой замене глубина схемы увеличится не более чем в <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/>
