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>n</tex>. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух следующим образом: <br/>
[[Файл:circuit.jpg]]
При замене каждого такого элемента глубина схемы увеличивается не более чем в <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>NC = AC</tex><br/>
Пусть <tex>L \in NC</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex>, где <tex>C_n</tex> размера <tex>N=O(poly(n))</tex> и имеет глубину <tex>O(log^d n)</tex>. Тогда возьмем параллельный компьютер с <tex>N</tex> процессорами, где каждый из них будет играть роль одного элемента схемы. Так как компьютер параллельный, то вычисления на каждом уровне схемы будут выполнятся параллельно. Тогда получаем, что всего потребуется <tex>O(log^d(n))</tex> времени.
Пусть <tex>L</tex> распознается параллельным компьютером с <tex>N=O(poly(n))</tex> процессоров за время <tex>D=O(log^d n)</tex>. Тогда построим схему глубины <tex>D</tex>, на каждом уровне которой будет по <tex>N</tex> элементов, таких, что <tex>i</tex>-й элемент на уровне <tex>t</tex> выполняет вычисления, производимые <tex>i</tex>-го процессора м процессором в момент времени <tex>t</tex>. Всего в схеме будет <tex>N \cdot D = O(poly(n)) \cdot O(log^d n) = O(poly(n))</tex> элементов.
}}
