Просмотр исходного текста страницы Классы NC и AC

==Введение==
Предположим у нас есть компьютер с <tex>poly(n)</tex> процессоров. Тогда актуально распараллелить полиномиальные вычисления, чтобы выполнять их не за <tex>poly(n)</tex> времени, а за <tex>poly(\log(n))</tex>. В качестве модели вычислений будем использовать логические схемы, но так как схема способна обрабатывать лишь входы заданной длины, то будем рассматривать семейства схем — по одной для каждой длины входа. Также потребуем, чтобы такую схему можно было эффективно построить на машине Тьюринга. Введем определения таких семейств, и соотнесем их с параллельными вычислениями.

==Определения==
{{Определение
|definition=
<tex>\mathrm{NC^i}</tex> — множество языков, распознаваемых семейством логических схем полиномиального от <tex>n</tex> размера, глубиной <tex>O(\log ^i (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} = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}</tex>.
}}

{{Определение
|definition=
<tex>\mathrm{AC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}</tex>.
}}

==Теоремы==
{{Теорема
|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> элементами со степенью входа не более 2 следующим образом:

[[Файл:AndCircuit.png|500px|center]]

При такой замене глубина схемы увеличится не более чем в <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>.

 
{{Теорема
|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> — неразрешенная на данный момент задача.


{{Утверждение
|about=тезис о связи <tex>\mathbf{NC}</tex> с параллельными алгоритмами
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(\log (n))</tex> тогда и только тогда, когда <tex>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> элементов.
}}

[[Категория: Теория сложности]]