Изменения

Пусть <tex>L \in NC</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> которые , таких, что существует детерминированная машина Тьюринга, строящая такую схему по <tex>1^n</tex> можно построить на , используя <tex>O(log(n))</tex> ячеек памяти . Конфигурация МТ задается положением головки исостоянием ячеек памяти, то есть у МТ может быть <tex>n \cdot 2^{O(log(n))} = O(n^2)</tex> конфигураций. При построении схемы конфигурации не могут повторяться, иначе МТ зациклится, следовательно, схема будет построена за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим ее. На вычисление схемы потребуется полином времени, так как схема полиномиального размера.}}

Пусть <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> элементов.