202
правки
Изменения
Нет описания правки
Предположим у нас есть компьютер с <tex>poly(n)</tex> процессоров. Тогда актуально распараллелить полиномиальные вычисления, чтобы выполнять их не за <tex>poly(n)</tex> времени, а за <tex>poly(\log(n))</tex>. В качестве модели вычислений будем использовать логические схемы, но так как схема способна обрабатывать лишь входы заданной длины, то будем рассматривать семейства схем — по одной для каждой длины входа. Также потребуем, чтобы такую схему можно было эффективно построить на машине Тьюринга. Введем определения таких семейств, и соотнесем их с параллельными вычислениями.
==Определения==
{{Определение
|definition=
<tex>\mathrm{NC^i = \mathcal{f} L \mid L — </tex> распознается — множество языков, распознаваемых семейством логических схем со степенью входа элемента не больше двух, размера полиномиального от <tex>poly(n)</tex> и глубины размера, глубиной <tex>O(\log^i (n))</tex> где <tex>n</tex> размер и со степенью входа. Причем такую схему можно построить по каждого элемента не более 2, причем существует детерминированная машина Тьюринга, принимающая на вход <tex>1^n</tex> на и строящая соответствующую схему используя <tex>O(\log(n))</tex> ячеек памяти, где <tex>n</tex> — длина входа.
}}
{{Определение
|definition=
<tex>\mathrm{AC^i}</tex> определяется аналогично <tex>\mathrm{NC^i}</tex>, только за исключением того, что степень входа элемента может быть неограничена, то есть элементы <tex>\mathrm{OR}</tex> и <tex>\mathrm{AND}</tex> могут иметь более двух входов.
}}
{{Определение
|definition=
<tex>\mathrm{NC } = \cupbigcup \limits_{i = 0}^{\infty}_\mathrm{i = 0} NC^i}</tex><br/>.}} {{Определение|definition=<tex>\mathrm{AC } = \cupbigcup \limits_{i = 0}^{\infty}_\mathrm{i = 0} AC^i}</tex><br/>.
}}
==Теоремы==
{{Теорема
|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>r(n)</tex>, поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более двух 2 следующим образом: <br/> [[Файл:circuitAndCircuit.jpgpng|500px|center]] При такой замене каждого такого элемента размер глубина схемы будет оставаться полиномиальнымувеличится не более чем в <tex>\log_2 r(n) = O(\log(n))</tex> раз, а так как изначально глубина увеличится на схемы была <tex>O(\log^i(n))</tex>, то после замены всех элементов она станет <tex>log_2 rO(\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> — неразрешенная на данный момент задача.
Пусть <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> элементов.
}}
