Классы NC и AC

Введение

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

Определения

Определение:

[math]\mathrm{NC^i}[/math] — множество языков, распознаваемых семейством логических схем полиномиального от [math]n[/math] размера, глубиной [math]O(\log ^i (n))[/math] и со степенью входа каждого элемента не более 2, причем существует детерминированная машина Тьюринга, принимающая на вход [math]1^n[/math] и строящая соответствующую схему используя [math]O(\log (n))[/math] ячеек памяти, где [math]n[/math] — длина входа.

Определение:

[math]\mathrm{AC^i}[/math] определяется аналогично [math]\mathrm{NC^i}[/math], за исключением того, что степень входа элемента может быть неограничена, то есть элементы [math]\mathrm{OR}[/math] и [math]\mathrm{AND}[/math] могут иметь более двух входов.

Определение:

[math]\mathrm{NC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}[/math].

Определение:

[math]\mathrm{AC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}[/math].

Теоремы

Теорема:

[math]\mathrm{NC^i} \subset \mathrm{AC^i} \subset \mathrm{NC^{i+1}}[/math].

Доказательство:

[math]\triangleright[/math]

[math]\mathrm{NC^i} \subset \mathrm{AC^i}[/math] Это понятно из определения [math]\mathrm{NC^i}[/math] и [math]\mathrm{AC^i}[/math]. [math]\mathrm{AC^i} \subset \mathrm{NC^{i+1}}[/math] Пусть [math]L \in \mathrm{AC^i}[/math]. [math]L[/math] распознается семейством схем [math]C_n[/math] полиномиального размера. Степень входа каждого элемента схемы [math]C_n[/math] не превосходит полинома от [math]n[/math], поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы [math]C_n[/math] элементами со степенью входа не более 2 следующим образом: При такой замене глубина схемы увеличится не более чем в [math]\log_2 r(n) = O(\log(n))[/math] раз, а так как изначально глубина схемы была [math]O(\log^i(n))[/math], то после замены всех элементов она станет [math]O(\log^i(n)) \cdot O(\log(n)) = O(\log^{i+1}(n))[/math]. При замене одного элемента будет добавлено не более [math]r(n)[/math] элементов, потому, поскольку изначальный размер схемы был полиномиальным и каждый элемент мы заменили полиномиальным числом элементов, после всех замен размер схемы останется полиномиальным.

[math]\triangleleft[/math]

Следствие: [math]\mathrm{NC} = \mathrm{AC}[/math].

Теорема:

[math]\mathrm{NC} \subseteq \mathrm{P}[/math].

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Равенство [math]\mathrm{NC}[/math] и [math]\mathrm{P}[/math] — неразрешенная на данный момент задача.

Утверждение (тезис о связи [math]\mathbf{NC}[/math] с параллельными алгоритмами):

[math]L[/math] распознается параллельным компьютером с [math]O(poly(n))[/math] процессоров за время [math]O(poly(\log (n))[/math] тогда и только тогда, когда [math]L \in \mathrm{NC}[/math].

[math]\triangleright[/math]

(набросок доказательства) Пусть [math]L \in \mathrm{NC}[/math]. [math]L[/math] распознается семейством схем [math]C_n[/math], где [math]C_n[/math] размера [math]N=O(poly(n))[/math] и имеет глубину [math]O(\log^d n)[/math]. Возьмем параллельный компьютер с [math]N[/math] процессорами, где каждый из них будет играть роль одного элемента схемы. Так как компьютер параллельный, то вычисления на каждом уровне схемы будут выполняться параллельно. Тогда получаем, что всего потребуется [math]O(\log^d(n))[/math] времени. Пусть [math]L[/math] распознается параллельным компьютером с [math]N=O(poly(n))[/math] процессоров за время [math]D=O(\log^d n)[/math]. Построим схему глубины [math]D[/math], на каждом уровне которой будет по [math]N[/math] элементов, таких, что [math]i[/math]-й элемент на уровне [math]t[/math] выполняет вычисления, производимые [math]i[/math]-м процессором в момент времени [math]t[/math]. Всего в схеме будет [math]N \cdot D = O(poly(n)) \cdot O(\log^d n) = O(poly(n))[/math] элементов.

[math]\triangleleft[/math]