Класс NC

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

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

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

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

Задачи в NC

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

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

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

Иерархия NC

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

[math]\displaystyle{ \mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots \subseteq \mathsf{NC}^i \subseteq \cdots \mathsf{NC}, }[/math]

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

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

[math]\displaystyle{ \mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC}^1 \subseteq \mathsf{NC}^2 \subseteq \mathsf{P}. }[/math]

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

[math]\displaystyle{ \mathsf{NC}^i \subseteq \mathsf{AC}^i \subseteq \mathsf{NC}^{i+1}. }[/math]

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

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

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

[math]\displaystyle{ \mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots }[/math]

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

1. [math]\displaystyle{ \mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i \subset \cdots \subset \mathsf{NC}^{i+j} \subset \cdots \mathsf{NC} }[/math]
2. [math]\displaystyle{ \mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i = \cdots = \mathsf{NC}^{i+j} = \cdots \mathsf{NC}. }[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ }[/math] Доказательство теоремы

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

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

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

Ссылки

• 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.