31
правка
Изменения
→Теоремы
'''Следствие:''' <tex>NC = AC</tex><br/>
{{Теорема
|statement=<tex>NC \subseteq P</tex>
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n)) \Leftrightarrow L \in NC</tex>.
|proof=
Пусть <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>.
}}
