Класс NC

В теории сложности вычислений классом NC (от англ. Nick’s Class) называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы $k$$k$ и $c$$c$ такие, что она может быть решена за время $O({\log }^c<!--\; \; -->n)$$O(\log ^{c}n)$ при использовании $O(n^k)$$O(n^{k})$ параллельных процессоров. Стивен Кук назвал его «Классом Ника» в честь Ника Пиппенжера^[en], который провел обширные исследования схем с полилогарифмической глубиной и полиномиальным размером.

Так же, как класс P можно считать классом податливых задач (Тезис Кобхэма^[en]), так и NC можно считать классом задач, которые могут быть эффективно решены на параллельном компьютере. NC — это подмножество P, потому что параллельные полилогарифмические вычисления можно симулировать с помощью последовательных полиномиальных вычислений. Неизвестно, верно ли NP = P, но большинство ученых считает, что нет, из чего следует, что скорее всего существуют податливые задачи, которые последовательны «от природы», и не могут быть существенно ускорены при использовании параллелизма. Так же, как класс NP-полных задач можно считать классом «скорее всего неподатливых» задач, так и класс P-полных задач, при сведении к NC, можно считать «скорее всего не параллелизуемым» или «скорее всего последовательным от природы».

Параллельный компьютер в определении можно считать параллельной машиной с произвольным доступом (PRAM — от англ. parallel, random-access machine). Это параллельный компьютер с центральным пулом памяти, любой процессор которого может получить доступ к любому биту за константное время. На определение NC не влияет способ, с помощью которого PRAM осуществляет одновременный доступ нескольких процессоров к одному биту.

NC может быть определён, как множество задач разрешимости, разрешимых распределённой Булевой схемой с полилогарифмической глубиной и полиномиальным числом вентилей.

Задачи в NCПравить

NC включает в себя много задач, в том числе:

• Сложение, умножение и деление целых чисел;
• Умножение матриц, подсчет их ранга, детерминанта, обратной матрицы;
• Полиномиальный НОД;
• Нахождение максимального паросочетания.

Часто алгоритмы для этих задач придумывались отдельно и не могли быть наивной адаптацией известных алгоритмов — Метод Гаусса и алгоритм Евклида полагаются на то, что операции выполняются последовательно.

Иерархия NCПравить

NCⁱ — это множество задач разрешимости, разрешимых распределенными булевыми схемами с полиномиальным количеством вентилей (с количеством входов, не большим двух) и глубиной $O({\log }^i<!--\; \; -->n)$$O(\log ^{i}n)$ , или разрешимых за время $O({\log }^i<!--\; \; -->n)$$O(\log ^{i}n)$  параллельным компьютером с полиномиальным числом процессоров. Очевидно,

${\mathsf{N}\mathsf{C}}^1\subseteq <!--\; \subseteq \; -->{\mathsf{N}\mathsf{C}}^2\subseteq <!--\; \subseteq \; -->\cdots <!--\; \cdots \; -->\subseteq <!--\; \subseteq \; -->{\mathsf{N}\mathsf{C}}^i\subseteq <!--\; \subseteq \; -->\cdots <!--\; \cdots \; -->\mathsf{N}\mathsf{C},$${\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}},$ 

что представляет собой NC-иерархию.

Мы можем связать классы NC с классами памяти L, NL и AC:

${\mathsf{N}\mathsf{C}}^1\subseteq <!--\; \subseteq \; -->\mathsf{L}\subseteq <!--\; \subseteq \; -->\mathsf{N}\mathsf{L}\subseteq <!--\; \subseteq \; -->{\mathsf{A}\mathsf{C}}^1\subseteq <!--\; \subseteq \; -->{\mathsf{N}\mathsf{C}}^2\subseteq <!--\; \subseteq \; -->\mathsf{P}.$${\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.$ 

Классы NC и AC одинаково определены, за исключением неограниченности количества входов у вентилей для класса AC. Для каждого $i$$i$  верно:

${\mathsf{N}\mathsf{C}}^i\subseteq <!--\; \subseteq \; -->{\mathsf{A}\mathsf{C}}^i\subseteq <!--\; \subseteq \; -->{\mathsf{N}\mathsf{C}}^{i+1}.$${\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.$ 

Следствием этого является NC = AC. Известно, что оба включения строгие для $i=0$$i=0$ . Похожим образом можем получить, что NC эквивалентен множеству задач, решаемых на переменной машине Тьюринга с числом выборов на каждом шаге не большим, чем двух, и с O(log n) памяти и $(\log <!--\; \; -->n{)}^{O(1)}$$(\log n)^{O(1)}$  альтерациями.

Нерешенная задача: является ли NC собственным?Править

Один из больших открытых вопросов теории сложности вычислений — является ли собственным каждое вложение NC-иерархии. Как было замечено Пападимитриу, если для какого-то $i$$i$  верно NCⁱ = NCⁱ⁺¹, то NCⁱ = NC^j для всех $j⩾<!--\; ⩾\; -->i$$j\geqslant i$ , и как следствие, NCⁱ = NC. Это наблюдение называется сворачиванием NC-иерархии, потому что даже из одного равенстве в цепи вложений:

${\mathsf{N}\mathsf{C}}^1\subseteq <!--\; \subseteq \; -->{\mathsf{N}\mathsf{C}}^2\subseteq <!--\; \subseteq \; -->\cdots <!--\; \cdots \; -->$${\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots$ 

следует, что вся NC-иерархия «сворачивается» до какого-то уровня $i$$i$ . Таким образом, возможны два варианта:

1. ${\mathsf{N}\mathsf{C}}^1\subset <!--\; \subset \; -->\cdots <!--\; \cdots \; -->\subset <!--\; \subset \; -->{\mathsf{N}\mathsf{C}}^i\subset <!--\; \subset \; -->\cdots <!--\; \cdots \; -->\subset <!--\; \subset \; -->{\mathsf{N}\mathsf{C}}^{i+j}\subset <!--\; \subset \; -->\cdots <!--\; \cdots \; -->\mathsf{N}\mathsf{C}$${\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}$ 
2. ${\mathsf{N}\mathsf{C}}^1\subset <!--\; \subset \; -->\cdots <!--\; \cdots \; -->\subset <!--\; \subset \; -->{\mathsf{N}\mathsf{C}}^i=\cdots <!--\; \cdots \; -->={\mathsf{N}\mathsf{C}}^{i+j}=\cdots <!--\; \cdots \; -->\mathsf{N}\mathsf{C}.$${\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}.$ 

Широко распространено мнение, что верно именно (1), хотя пока не обнаружено никаких доказательств в отношении истинности того или иного утверждения.

Теорема БаррингтонаПравить

Ветвящаяся программа с $n$$n$  переменными, шириной $k$$k$  и длиной $m$$m$  состоит из последовательности инструкций длины $m$$m$ . Каждая инструкция — это тройка $(i,p,q)$$(i,p,q)$ , где $i$$i$  — это индекс переменной, которую нужно проверить $(1\le <!--\; \le \; -->i\le <!--\; \le \; -->n)$$(1\leq i\leq n)$ , а $p$$p$  и $q$$q$  — это функции перестановки из $\{1,2,...,k\}$$\{1,2,...,k\}$  в $\{1,2,...,k\}$$\{1,2,...,k\}$ . Числа $1,2,...,k$$1,2,...,k$  называются состояниями ветвящейся программы. Программа начинается в состоянии 1, и каждая инструкция $(i,p,q)$$(i,p,q)$  изменяет состояние $x$$x$  в $p(x)$$p(x)$  или $q(x)$$q(x)$ , в зависимости от того, равна ли $i$$i$ -ая переменная 0 или 1.

Семейство ветвящихся программ состоит из ветвящихся программ с $n$$n$  переменными для каждого $n$$n$ .

Легко показать, что любой язык $L$$L$  на $\{0,1\}$$\{0,1\}$  может быть распознан семейством ветвящихся программ с шириной 5 и экспоненциальной длиной, или семейством с экспоненциальной шириной и линейной длиной.

Каждый регулярный язык на $\{0,1\}$$\{0,1\}$  может быть распознан семейством ветвящихся программ с константной шириной и линейным числом инструкций (так как ДКА может быть преобразован в ветвящуюся программу). BWBP обозначает класс языков, распознаваемых семейством ветвящихся программ с ограниченной шириной и полиномиальной длиной (англ BWBP — bounded width and polynomial length)..

Теорема Баррингтона утверждает, что BWBP — это в точности нераспределенный NC¹. Доказательство теоремы использует неразрешимость группы симметрии $S_5$$S_{5}$ .

Доказательство теоремы БаррингтонаПравить

Докажем, что ветвящаяся программа (ВП) с константной шириной и полиномиальным размером может быть превращена в схему из NC¹.

От противного: пусть есть схема C из NC¹. Без ограничения общности, будем считать что в ней используются только вентили И и НЕ.

Определение: ВП называется $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -вычисляющей булеву функцию $f$$f$  или $(\mathrm{\sigma <!--\; \sigma \; -->}-<!--\; -\; -->f)$$(\sigma -f)$ , если при $f=0$$f=0$  она дает результат — тождественную перестановку, а при $f=1$$f=1$  её результат — $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -перестановка. Так как наша схема C описывает какую-то булеву функцию $f$$f$  и только её, можем взаимно заменять эти термины.

Для доказательства будем использовать две леммы:

Лемма 1: Если есть ВП, $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -вычисляющая $f$$f$ , то существует и ВП, ${\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\sigma ^{-1}$ -вычисляющая $f$$f$  (то есть, равная $id$$id$  при $f=0$$f=0$ , и равная ${\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\sigma ^{-1}$  при $f=1$$f=1$ .

Доказательство: так как $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  и ${\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\sigma ^{-1}$  — циклы, а любые два цикла являются сопряженными, то существует такая перестановка $\mathrm{\pi <!--\; \pi \; -->}$$\pi$ , что ${\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\sigma ^{-1}$  = $\mathrm{\pi <!--\; \pi \; -->}\mathrm{\sigma <!--\; \sigma \; -->}{\mathrm{\pi <!--\; \pi \; -->}}^{-<!--\; -\; -->1}$$\pi \sigma \pi ^{-1}$ . Тогда домножим на $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  перестановки $p_1$$p_{1}$  и $q_1$$q_{1}$  из первой инструкции ВП слева (чтобы получить перестановки $\mathrm{\pi <!--\; \pi \; -->}{p}_1$${\pi }p_{1}$  и $\mathrm{\pi <!--\; \pi \; -->}{q}_1$${\pi }q_{1}$ ), а перестановки из последней инструкции домножим на ${\mathrm{\pi <!--\; \pi \; -->}}^{-<!--\; -\; -->1}$$\pi ^{-1}$  справа (получим $p_n{\mathrm{\pi <!--\; \pi \; -->}}^{-<!--\; -\; -->1}$$p_{n}\pi ^{-1}$  и $q_n{\mathrm{\pi <!--\; \pi \; -->}}^{-<!--\; -\; -->1}$$q_{n}\pi ^{-1}$ ). Если до наших действий (без ограничения общности) $p_1{p}_2...p_n$${p_{1}}{p_{2}}...{p_{n}}$  был равен $id$$id$ , то теперь результат будет $\mathrm{\pi <!--\; \pi \; -->}id{\mathrm{\pi <!--\; \pi \; -->}}^{-<!--\; -\; -->1}=id$${\pi }id{\pi }^{-1}=id$ , а если был равен $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ , то результат равен $\mathrm{\pi <!--\; \pi \; -->}\mathrm{\sigma <!--\; \sigma \; -->}{\mathrm{\pi <!--\; \pi \; -->}}^{-<!--\; -\; -->1}={\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\pi \sigma \pi ^{-1}=\sigma ^{-1}$ . Так, мы получили ВП, ${\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\sigma ^{-1}$ -вычисляющую $f$$f$ , с той же длиной (количество инструкций не поменялось).

Примечание: если домножить вывод ВП $({\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}-<!--\; -\; -->f)$$(\sigma ^{-1}-f)$  на $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  справа, то очевидным образом получим ВП, $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -вычисляющую функцию $\mathrm{\neg <!--\; \neg \; -->}f$${\neg }f$ .

Лемма 2: Если есть два ВП: $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -вычисляющая $f$$f$  и $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$ -вычисляющая $t$$t$  с длинами $l_1$$l_{1}$  и $l_2$$l_{2}$ , где $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  и $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$  — 5-цикличные перестановки, то существует ВП с 5-цикличной перестановкой $\mathrm{\epsilon <!--\; \epsilon \; -->}=\mathrm{\gamma <!--\; \gamma \; -->}\mathrm{\sigma <!--\; \sigma \; -->}{\mathrm{\gamma <!--\; \gamma \; -->}}^{-<!--\; -\; -->1}{\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}$  такая, что ВП $\mathrm{\epsilon <!--\; \epsilon \; -->}$$\varepsilon$ -вычисляет$f\wedge <!--\; \wedge \; -->t$$f{\wedge }t$ , и её размер не превосходит $2(l_1$$2(l_{1}$  + $l_2)$$l_{2})$ .

Доказательство: Выложим «в ряд» инструкции четырёх ВП: $(\mathrm{\gamma <!--\; \gamma \; -->}-<!--\; -\; -->t)$$(\gamma -t)$ , $(\mathrm{\sigma <!--\; \sigma \; -->}-<!--\; -\; -->f)$$(\sigma -f)$ , $({\mathrm{\gamma <!--\; \gamma \; -->}}^{-<!--\; -\; -->1}-<!--\; -\; -->t)$$(\gamma ^{-1}-t)$ , $({\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}-<!--\; -\; -->f)$$(\sigma ^{-1}-f)$  (строим обратные по лемме 1). Если одна или обе функции выдают 0, то результат большой программы $\mathrm{\epsilon <!--\; \epsilon \; -->}=id$$\varepsilon =id$ : например, при $f=0,t=1,\mathrm{\epsilon <!--\; \epsilon \; -->}=id\mathrm{\sigma <!--\; \sigma \; -->}id{\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}=id$$f=0,t=1,\varepsilon =id{\sigma }id{\sigma }^{-1}=id$ . Если обе функции выдают 1, то $\mathrm{\epsilon <!--\; \epsilon \; -->}=\mathrm{\gamma <!--\; \gamma \; -->}\mathrm{\sigma <!--\; \sigma \; -->}{\mathrm{\gamma <!--\; \gamma \; -->}}^{-<!--\; -\; -->1}{\mathrm{\sigma <!--\; \sigma \; -->}}^{-<!--\; -\; -->1}$$\varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}$ . Здесь $\gamma \sigma \gamma ^{-1}\sigma ^{-1}\neq id<=>\gamma \sigma \neq \sigma \gamma$ , что верно из-за того, что эти перестановки 5-цикличны (из-за неразрешимости группы симметрии $S_5$$S_{5}$ ). Длина новой ВП высчитывается по определению.

${\displaystyle }$ Доказательство теоремы

Будем доказывать по индукции. Предположим, что у нас есть схема C с входами $x_1,...,x_n$$x_{1},...,x_{n}$  и что для всех подсхем D и 5-цикличных перестановок $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  существует ВП, $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -вычисляющая D. Покажем, что для всех 5-перестановок $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  существует ВП, $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -вычисляющий C.

• Если схема C выдает $x_i$$x_{i}$ , то ВП имеет одну инструкцию: проверить значение $x_i$$x_{i}$  (0 или 1), и отдать $id$$id$  или $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  (соответственно).
• Если схема C выдает $\mathrm{\neg <!--\; \neg \; -->}$$\neg$ A для какой-то другой схемы A, по примечанию к лемме 1 создадим ВП, $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ -вычисляющую $\mathrm{\neg <!--\; \neg \; -->}$$\neg$ A.
• Если схема C выдает A$\wedge <!--\; \wedge \; -->$$\wedge$ B для схем A и B, создадим нужную ВП по лемме 2.

Размер итоговой ветвящейся программы не превосходит $4^d$$4^{d}$ , где $d$$d$  — это глубина схемы. Если у схемы логарифмическая глубина, то у ВП полиномиальная длина.

СсылкиПравить

• Arora, Sanjeev. Computational complexity. A modern approach / Sanjeev Arora, Boaz Barak. — Cambridge University Press, 2009. — ISBN 978-0-521-42426-4.
• Clote, Peter. Boolean functions and computation models / Peter Clote, Evangelos Kranakis. — Berlin : Springer-Verlag, 2002. — ISBN 3-540-59436-1.
• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. Архивная копия от 4 июня 2013 на Wayback Machine ISBN 0-19-508591-4
• Kozen, Dexter C. The design and analysis of algorithms. — 1992. Lectures 28 — 34 and 36
• Kozen, Dexter C. Theory of Computation. — Springer-Verlag, 2006. — ISBN 1-84628-297-7. Lecture 12: Relation of NC to Time-Space Classes
• Papadimitriou, Christos. Section 15.3: The class NC // Computational Complexity. — 1st. — Addison Wesley, 1993. — P. 375–381. — ISBN 0-201-53082-1.
• Straubing, Howard. Finite automata, formal logic, and circuit complexity. — Basel : Birkhäuser, 1994. — ISBN 3-7643-3719-2.
• Vollmer, Heribert. Introduction to circuit complexity. A uniform approach. — Berlin : Springer-Verlag, 1998. — ISBN 3-540-64310-9.