Класс NC

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

Так же, как класс P можно считать классом податливых задач (Шаблон:Iw), так и 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)$ параллельным компьютером с полиномиальным числом процессоров. Очевидно,

${𝖭𝖢}^1\subseteq {𝖭𝖢}^2\subseteq \cdots \subseteq {𝖭𝖢}^i\subseteq \cdots 𝖭𝖢,$

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

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

${𝖭𝖢}^1\subseteq 𝖫\subseteq 𝖭𝖫\subseteq {𝖠𝖢}^1\subseteq {𝖭𝖢}^2\subseteq 𝖯.$

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

${𝖭𝖢}^i\subseteq {𝖠𝖢}^i\subseteq {𝖭𝖢}^{i+1}.$

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

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

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

${𝖭𝖢}^1\subseteq {𝖭𝖢}^2\subseteq \cdots$

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

1. ${𝖭𝖢}^1\subset \cdots \subset {𝖭𝖢}^i\subset \cdots \subset {𝖭𝖢}^{i+j}\subset \cdots 𝖭𝖢$
2. ${𝖭𝖢}^1\subset \cdots \subset {𝖭𝖢}^i=\cdots ={𝖭𝖢}^{i+j}=\cdots 𝖭𝖢.$

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

Теорема Баррингтона

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

• Шаблон:Cite book
• Шаблон:Cite book
• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. Шаблон:Wayback Шаблон:Isbn
• Шаблон:Cite book Lectures 28 — 34 and 36
• Шаблон:Cite book Lecture 12: Relation of NC to Time-Space Classes
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book