В теории сложности вычислений классом NC (от англ. Nick’s Class) называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы k {\displaystyle k} и c {\displaystyle c} такие, что она может быть решена за время O ( log c --> n ) {\displaystyle O(\log ^{c}n)} при использовании O ( n k ) {\displaystyle O(n^{k})} параллельных процессоров. Стивен Кук[1][2] назвал его «Классом Ника» в честь Ника Пиппенжера[англ.], который провел обширные исследования[3] схем с полилогарифмической глубиной и полиномиальным размером.[4]
Так же, как класс P можно считать классом податливых задач (Тезис Кобхэма[англ.]), так и NC можно считать классом задач, которые могут быть эффективно решены на параллельном компьютере.[5] NC — это подмножество P, потому что параллельные полилогарифмические вычисления можно симулировать с помощью последовательных полиномиальных вычислений. Неизвестно, верно ли NP = P, но большинство ученых считает, что нет, из чего следует, что скорее всего существуют податливые задачи, которые последовательны «от природы», и не могут быть существенно ускорены при использовании параллелизма. Так же, как класс NP-полных задач можно считать классом «скорее всего неподатливых» задач, так и класс P-полных задач, при сведении к NC, можно считать «скорее всего не параллелизуемым» или «скорее всего последовательным от природы».
Параллельный компьютер в определении можно считать параллельной машиной с произвольным доступом (PRAM — от англ. parallel, random-access machine). Это параллельный компьютер с центральным пулом памяти, любой процессор которого может получить доступ к любому биту за константное время. На определение NC не влияет способ, с помощью которого PRAM осуществляет одновременный доступ нескольких процессоров к одному биту.
NC может быть определён, как множество задач разрешимости, разрешимых распределённой Булевой схемой с полилогарифмической глубиной и полиномиальным числом вентилей.
NC включает в себя много задач, в том числе:
Часто алгоритмы для этих задач придумывались отдельно и не могли быть наивной адаптацией известных алгоритмов — Метод Гаусса и алгоритм Евклида полагаются на то, что операции выполняются последовательно.
NCi — это множество задач разрешимости, разрешимых распределенными булевыми схемами с полиномиальным количеством вентилей (с количеством входов, не большим двух) и глубиной O ( log i --> n ) {\displaystyle O(\log ^{i}n)} , или разрешимых за время O ( log i --> n ) {\displaystyle O(\log ^{i}n)} параллельным компьютером с полиномиальным числом процессоров. Очевидно,
что представляет собой NC-иерархию.
Мы можем связать классы NC с классами памяти L, NL[6] и AC[7]:
Классы NC и AC одинаково определены, за исключением неограниченности количества входов у вентилей для класса AC. Для каждого i {\displaystyle i} верно[5][7]:
Следствием этого является NC = AC.[8] Известно, что оба включения строгие для i = 0 {\displaystyle i=0} .[5] Похожим образом можем получить, что NC эквивалентен множеству задач, решаемых на переменной машине Тьюринга с числом выборов на каждом шаге не большим, чем двух, и с O(log n) памяти и ( log --> n ) O ( 1 ) {\displaystyle (\log n)^{O(1)}} альтерациями.[9]
Один из больших открытых вопросов теории сложности вычислений — является ли собственным каждое вложение NC-иерархии. Как было замечено Пападимитриу, если для какого-то i {\displaystyle i} верно NCi = NCi+1, то NCi = NCj для всех j ⩾ ⩾ --> i {\displaystyle j\geqslant i} , и как следствие, NCi = NC. Это наблюдение называется сворачиванием NC-иерархии, потому что даже из одного равенстве в цепи вложений:
следует, что вся NC-иерархия «сворачивается» до какого-то уровня i {\displaystyle i} . Таким образом, возможны два варианта:
Широко распространено мнение, что верно именно (1), хотя пока не обнаружено никаких доказательств в отношении истинности того или иного утверждения.
Ветвящаяся программа с n {\displaystyle n} переменными, шириной k {\displaystyle k} и длиной m {\displaystyle m} состоит из последовательности инструкций длины m {\displaystyle m} . Каждая инструкция — это тройка ( i , p , q ) {\displaystyle (i,p,q)} , где i {\displaystyle i} — это индекс переменной, которую нужно проверить ( 1 ≤ ≤ --> i ≤ ≤ --> n ) {\displaystyle (1\leq i\leq n)} , а p {\displaystyle p} и q {\displaystyle q} — это функции перестановки из { 1 , 2 , . . . , k } {\displaystyle \{1,2,...,k\}} в { 1 , 2 , . . . , k } {\displaystyle \{1,2,...,k\}} . Числа 1 , 2 , . . . , k {\displaystyle 1,2,...,k} называются состояниями ветвящейся программы. Программа начинается в состоянии 1, и каждая инструкция ( i , p , q ) {\displaystyle (i,p,q)} изменяет состояние x {\displaystyle x} в p ( x ) {\displaystyle p(x)} или q ( x ) {\displaystyle q(x)} , в зависимости от того, равна ли i {\displaystyle i} -ая переменная 0 или 1.
Семейство ветвящихся программ состоит из ветвящихся программ с n {\displaystyle n} переменными для каждого n {\displaystyle n} .
Легко показать, что любой язык L {\displaystyle L} на { 0 , 1 } {\displaystyle \{0,1\}} может быть распознан семейством ветвящихся программ с шириной 5 и экспоненциальной длиной, или семейством с экспоненциальной шириной и линейной длиной.
Каждый регулярный язык на { 0 , 1 } {\displaystyle \{0,1\}} может быть распознан семейством ветвящихся программ с константной шириной и линейным числом инструкций (так как ДКА может быть преобразован в ветвящуюся программу). BWBP обозначает класс языков, распознаваемых семейством ветвящихся программ с ограниченной шириной и полиномиальной длиной (англ BWBP — bounded width and polynomial length).[10].
Теорема Баррингтона[11] утверждает, что BWBP — это в точности нераспределенный NC1. Доказательство теоремы использует неразрешимость группы симметрии S 5 {\displaystyle S_{5}} .[10]
Докажем, что ветвящаяся программа (ВП) с константной шириной и полиномиальным размером может быть превращена в схему из NC1.
От противного: пусть есть схема C из NC1. Без ограничения общности, будем считать что в ней используются только вентили И и НЕ.
Определение: ВП называется σ σ --> {\displaystyle \sigma } -вычисляющей булеву функцию f {\displaystyle f} или ( σ σ --> − − --> f ) {\displaystyle (\sigma -f)} , если при f = 0 {\displaystyle f=0} она дает результат — тождественную перестановку, а при f = 1 {\displaystyle f=1} её результат — σ σ --> {\displaystyle \sigma } -перестановка. Так как наша схема C описывает какую-то булеву функцию f {\displaystyle f} и только её, можем взаимно заменять эти термины.
Для доказательства будем использовать две леммы:
Лемма 1: Если есть ВП, σ σ --> {\displaystyle \sigma } -вычисляющая f {\displaystyle f} , то существует и ВП, σ σ --> − − --> 1 {\displaystyle \sigma ^{-1}} -вычисляющая f {\displaystyle f} (то есть, равная i d {\displaystyle id} при f = 0 {\displaystyle f=0} , и равная σ σ --> − − --> 1 {\displaystyle \sigma ^{-1}} при f = 1 {\displaystyle f=1} .
Доказательство: так как σ σ --> {\displaystyle \sigma } и σ σ --> − − --> 1 {\displaystyle \sigma ^{-1}} — циклы, а любые два цикла являются сопряженными, то существует такая перестановка π π --> {\displaystyle \pi } , что σ σ --> − − --> 1 {\displaystyle \sigma ^{-1}} = π π --> σ σ --> π π --> − − --> 1 {\displaystyle \pi \sigma \pi ^{-1}} . Тогда домножим на π π --> {\displaystyle \pi } перестановки p 1 {\displaystyle p_{1}} и q 1 {\displaystyle q_{1}} из первой инструкции ВП слева (чтобы получить перестановки π π --> p 1 {\displaystyle {\pi }p_{1}} и π π --> q 1 {\displaystyle {\pi }q_{1}} ), а перестановки из последней инструкции домножим на π π --> − − --> 1 {\displaystyle \pi ^{-1}} справа (получим p n π π --> − − --> 1 {\displaystyle p_{n}\pi ^{-1}} и q n π π --> − − --> 1 {\displaystyle q_{n}\pi ^{-1}} ). Если до наших действий (без ограничения общности) p 1 p 2 . . . p n {\displaystyle {p_{1}}{p_{2}}...{p_{n}}} был равен i d {\displaystyle id} , то теперь результат будет π π --> i d π π --> − − --> 1 = i d {\displaystyle {\pi }id{\pi }^{-1}=id} , а если был равен σ σ --> {\displaystyle \sigma } , то результат равен π π --> σ σ --> π π --> − − --> 1 = σ σ --> − − --> 1 {\displaystyle \pi \sigma \pi ^{-1}=\sigma ^{-1}} . Так, мы получили ВП, σ σ --> − − --> 1 {\displaystyle \sigma ^{-1}} -вычисляющую f {\displaystyle f} , с той же длиной (количество инструкций не поменялось).
Примечание: если домножить вывод ВП ( σ σ --> − − --> 1 − − --> f ) {\displaystyle (\sigma ^{-1}-f)} на σ σ --> {\displaystyle \sigma } справа, то очевидным образом получим ВП, σ σ --> {\displaystyle \sigma } -вычисляющую функцию ¬ ¬ --> f {\displaystyle {\neg }f} .
Лемма 2: Если есть два ВП: σ σ --> {\displaystyle \sigma } -вычисляющая f {\displaystyle f} и γ γ --> {\displaystyle \gamma } -вычисляющая t {\displaystyle t} с длинами l 1 {\displaystyle l_{1}} и l 2 {\displaystyle l_{2}} , где σ σ --> {\displaystyle \sigma } и γ γ --> {\displaystyle \gamma } — 5-цикличные перестановки, то существует ВП с 5-цикличной перестановкой ε ε --> = γ γ --> σ σ --> γ γ --> − − --> 1 σ σ --> − − --> 1 {\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}} такая, что ВП ε ε --> {\displaystyle \varepsilon } -вычисляет f ∧ ∧ --> t {\displaystyle f{\wedge }t} , и её размер не превосходит 2 ( l 1 {\displaystyle 2(l_{1}} + l 2 ) {\displaystyle l_{2})} .
Доказательство: Выложим «в ряд» инструкции четырёх ВП: ( γ γ --> − − --> t ) {\displaystyle (\gamma -t)} , ( σ σ --> − − --> f ) {\displaystyle (\sigma -f)} , ( γ γ --> − − --> 1 − − --> t ) {\displaystyle (\gamma ^{-1}-t)} , ( σ σ --> − − --> 1 − − --> f ) {\displaystyle (\sigma ^{-1}-f)} (строим обратные по лемме 1). Если одна или обе функции выдают 0, то результат большой программы ε ε --> = i d {\displaystyle \varepsilon =id} : например, при f = 0 , t = 1 , ε ε --> = i d σ σ --> i d σ σ --> − − --> 1 = i d {\displaystyle f=0,t=1,\varepsilon =id{\sigma }id{\sigma }^{-1}=id} . Если обе функции выдают 1, то ε ε --> = γ γ --> σ σ --> γ γ --> − − --> 1 σ σ --> − − --> 1 {\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1}} . Здесь γ γ --> σ σ --> γ γ --> − − --> 1 σ σ --> − − --> 1 ≠ ≠ --> i d <=> γ γ --> σ σ --> ≠ ≠ --> σ σ --> γ γ --> {\displaystyle \gamma \sigma \gamma ^{-1}\sigma ^{-1}\neq id<=>\gamma \sigma \neq \sigma \gamma } , что верно из-за того, что эти перестановки 5-цикличны (из-за неразрешимости группы симметрии S 5 {\displaystyle S_{5}} ). Длина новой ВП высчитывается по определению.
{\displaystyle } Доказательство теоремы
Будем доказывать по индукции. Предположим, что у нас есть схема C с входами x 1 , . . . , x n {\displaystyle x_{1},...,x_{n}} и что для всех подсхем D и 5-цикличных перестановок σ σ --> {\displaystyle \sigma } существует ВП, σ σ --> {\displaystyle \sigma } -вычисляющая D. Покажем, что для всех 5-перестановок σ σ --> {\displaystyle \sigma } существует ВП, σ σ --> {\displaystyle \sigma } -вычисляющий C.
Размер итоговой ветвящейся программы не превосходит 4 d {\displaystyle 4^{d}} , где d {\displaystyle d} — это глубина схемы. Если у схемы логарифмическая глубина, то у ВП полиномиальная длина.
{{cite journal}}
|journal=
Lokasi Pengunjung: 18.216.26.192