31
правка
Изменения
→Теоремы
==Теоремы==
{{Теорема
|statement=<tex>\mathrm{NC^i } \subset \mathrm{AC^i } \subset \mathrm{NC^{i+1}}</tex>
|proof=
*<tex>\mathrm{NC^i } \subset \mathrm{AC^i}</tex> <br/>Это понятно из определения <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> элементами со степенью входа не более двух следующим образом: <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>\mathrm{NC } = \mathrm{AC}</tex><br/>
{{Теорема
|statement=<tex>\mathrm{NC } \subseteq \mathrm{P}</tex>
|proof =
Пусть <tex>L \in \mathrm{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>\mathrm{NC}</tex> и <tex>\mathrm{P}</tex> — неразрешенная на данный момент задача.
{{Теорема
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n)) \Leftrightarrow L \in \mathrm{NC}</tex>.
|proof=
Пусть <tex>L \in \mathrm{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> элементов.
}}
