31
правка
Изменения
→Теоремы
Пусть <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>и размер схемы останется полиномиальным.
}}
'''Следствие:''' <tex>NC = AC</tex><br/>
|proof =
Пусть <tex>L \in NC</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> которые по <tex>1^n</tex> можно построить на <tex>O(log(n))</tex> памяти и, следовательно, за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим ее.}}
Равенство <tex>NC</tex> и <tex>P</tex> — неразрешенная на данный момент задача.
