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

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

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

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

Задачи в NC

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

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

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

Иерархия NC

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

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}},}$

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

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

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.}$

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

${\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.}$

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

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

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

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots }$

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

1. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}}$
2. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размер итоговой ветвящейся программы не превосходит ${\displaystyle 4^{d}}$ , где ${\displaystyle 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 .
• от 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 // . — 1st. — Addison Wesley, 1993. — P. –381. — ISBN 0-201-53082-1 .
• Straubing, Howard. . — 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 .