В теории сложности вычислений классом NC (от англ. Nick’s Class) называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы и такие, что она может быть решена за время при использовании параллельных процессоров. Стивен Кук назвал его «Классом Ника» в честь , который провел обширные исследования схем с полилогарифмической глубиной и полиномиальным размером.Arora & Barak (2009) p.120
Так же, как класс P можно считать классом податливых задач (), так и NC можно считать классом задач, которые могут быть эффективно решены на параллельном компьютере.Arora & Barak (2009) p.118 NC — это подмножество P, потому что параллельные полилогарифмические вычисления можно симулировать с помощью последовательных полиномиальных вычислений. Неизвестно, верно ли NP = P, но большинство ученых считает, что нет, из чего следует, что скорее всего существуют податливые задачи, которые последовательны «от природы», и не могут быть существенно ускорены при использовании параллелизма. Так же, как класс NP-полных задач можно считать классом «скорее всего неподатливых» задач, так и класс P-полных задач, при сведении к NC, можно считать «скорее всего не параллелизуемым» или «скорее всего последовательным от природы».
Параллельный компьютер в определении можно считать параллельной машиной с произвольным доступом (PRAM — от англ. parallel, random-access machine). Это параллельный компьютер с центральным пулом памяти, любой процессор которого может получить доступ к любому биту за константное время. На определение NC не влияет способ, с помощью которого PRAM осуществляет одновременный доступ нескольких процессоров к одному биту.
NC может быть определён, как множество задач разрешимости, разрешимых распределённой Булевой схемой с полилогарифмической глубиной и полиномиальным числом вентилей.
Задачи в NC NC включает в себя много задач, в том числе: Сложение, умножение и деление целых чисел; Умножение матриц, подсчет их ранга, детерминанта, обратной матрицы; Полиномиальный НОД; Нахождение максимального паросочетания.
Часто алгоритмы для этих задач придумывались отдельно и не могли быть наивной адаптацией известных алгоритмов — Метод Гаусса и алгоритм Евклида полагаются на то, что операции выполняются последовательно.
Иерархия NC NCi — это множество задач разрешимости, разрешимых распределенными булевыми схемами с полиномиальным количеством вентилей (с количеством входов, не большим двух) и глубиной , или разрешимых за время параллельным компьютером с полиномиальным числом процессоров. Очевидно,
что представляет собой NC-иерархию.
Мы можем связать классы NC с классами памяти L, NLPapadimitriou (1994) Theorem 16.1 и ACClote & Kranakis (2002) p.437:
Классы NC и AC одинаково определены, за исключением неограниченности количества входов у вентилей для класса AC. Для каждого верно:
Следствием этого является NC = AC.Clote & Kranakis (2002) p.12 Известно, что оба включения строгие для . Похожим образом можем получить, что NC эквивалентен множеству задач, решаемых на переменной машине Тьюринга с числом выборов на каждом шаге не большим, чем двух, и с O(log n) памяти и альтерациями.
Нерешенная задача: является ли NC собственным? Один из больших открытых вопросов теории сложности вычислений — является ли собственным каждое вложение NC-иерархии. Как было замечено Пападимитриу, если для какого-то верно NCi = NCi+1, то NCi = NCj для всех , и как следствие, NCi = NC. Это наблюдение называется сворачиванием NC-иерархии, потому что даже из одного равенстве в цепи вложений:
следует, что вся NC-иерархия «сворачивается» до какого-то уровня . Таким образом, возможны два варианта:
Широко распространено мнение, что верно именно (1), хотя пока не обнаружено никаких доказательств в отношении истинности того или иного утверждения.
Теорема Баррингтона Ветвящаяся программа с переменными, шириной и длиной состоит из последовательности инструкций длины . Каждая инструкция — это тройка , где — это индекс переменной, которую нужно проверить , а и — это функции перестановки из в . Числа называются состояниями ветвящейся программы. Программа начинается в состоянии 1, и каждая инструкция изменяет состояние в или , в зависимости от того, равна ли -ая переменная 0 или 1.
Семейство ветвящихся программ состоит из ветвящихся программ с переменными для каждого .
Легко показать, что любой язык на может быть распознан семейством ветвящихся программ с шириной 5 и экспоненциальной длиной, или семейством с экспоненциальной шириной и линейной длиной.
Каждый регулярный язык на может быть распознан семейством ветвящихся программ с константной шириной и линейным числом инструкций (так как ДКА может быть преобразован в ветвящуюся программу). BWBP обозначает класс языков, распознаваемых семейством ветвящихся программ с ограниченной шириной и полиномиальной длиной (англ BWBP — bounded width and polynomial length).Clote & Kranakis (2002) p.50.
Теорема Баррингтона утверждает, что BWBP — это в точности нераспределенный NC1. Доказательство теоремы использует неразрешимость группы симметрии .
Доказательство теоремы Баррингтона Докажем, что ветвящаяся программа (ВП) с константной шириной и полиномиальным размером может быть превращена в схему из NC1.
От противного: пусть есть схема C из NC1. Без ограничения общности, будем считать что в ней используются только вентили И и НЕ.
Определение: ВП называется -вычисляющей булеву функцию или , если при она дает результат — тождественную перестановку, а при её результат — -перестановка. Так как наша схема C описывает какую-то булеву функцию и только её, можем взаимно заменять эти термины.
Для доказательства будем использовать две леммы:
Лемма 1: Если есть ВП, -вычисляющая , то существует и ВП, -вычисляющая (то есть, равная при , и равная при .
Доказательство: так как и — циклы, а любые два цикла являются сопряженными, то существует такая перестановка , что = . Тогда домножим на перестановки и из первой инструкции ВП слева (чтобы получить перестановки и ), а перестановки из последней инструкции домножим на справа (получим и ). Если до наших действий (без ограничения общности) был равен , то теперь результат будет , а если был равен , то результат равен . Так, мы получили ВП, -вычисляющую , с той же длиной (количество инструкций не поменялось).
Примечание: если домножить вывод ВП на справа, то очевидным образом получим ВП, -вычисляющую функцию .
Лемма 2: Если есть два ВП: -вычисляющая и -вычисляющая с длинами и , где и — 5-цикличные перестановки, то существует ВП с 5-цикличной перестановкой такая, что ВП -вычисляет, и её размер не превосходит + .
Доказательство: Выложим «в ряд» инструкции четырёх ВП: , , , (строим обратные по лемме 1). Если одна или обе функции выдают 0, то результат большой программы : например, при . Если обе функции выдают 1, то . Здесь , что верно из-за того, что эти перестановки 5-цикличны (из-за неразрешимости группы симметрии ). Длина новой ВП высчитывается по определению.
Доказательство теоремы
Будем доказывать по индукции. Предположим, что у нас есть схема C с входами и что для всех подсхем D и 5-цикличных перестановок существует ВП, -вычисляющая D. Покажем, что для всех 5-перестановок существует ВП, -вычисляющий C. Если схема C выдает , то ВП имеет одну инструкцию: проверить значение (0 или 1), и отдать или (соответственно). Если схема C выдает A для какой-то другой схемы A, по примечанию к лемме 1 создадим ВП, -вычисляющую A. Если схема C выдает AB для схем A и B, создадим нужную ВП по лемме 2.
Размер итоговой ветвящейся программы не превосходит , где — это глубина схемы. Если у схемы логарифмическая глубина, то у ВП полиномиальная длина.
Примечания
Ссылки
Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. Lectures 28 — 34 and 36 Lecture 12: Relation of NC to Time-Space Classes
Категория:Классы сложности