Класс NC

Перейти к навигацииПерейти к поиску

В теории сложности вычислений классом NC (от англ. Nick’s Class) называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы и такие, что она может быть решена за время при использовании параллельных процессоров. Стивен Кук[1][2] назвал его «Классом Ника» в честь Ника Пиппенжера[англ.], который провел обширные исследования[3] схем с полилогарифмической глубиной и полиномиальным размером.[4]

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

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

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

Задачи в NC

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

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

Иерархия NC

NCi — это множество задач разрешимости, разрешимых распределенными булевыми схемами с полиномиальным количеством вентилей (с количеством входов, не большим двух) и глубиной , или разрешимых за время параллельным компьютером с полиномиальным числом процессоров. Очевидно,

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

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

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

Следствием этого является NC = AC.[8] Известно, что оба включения строгие для .[5] Похожим образом можем получить, что NC эквивалентен множеству задач, решаемых на переменной машине Тьюринга с числом выборов на каждом шаге не большим, чем двух, и с O(log n) памяти и альтерациями.[9]

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

Один из больших открытых вопросов теории сложности вычислений — является ли собственным каждое вложение NC-иерархии. Как было замечено Пападимитриу, если для какого-то верно NCi = NCi+1, то NCi = NCj для всех , и как следствие, NCi = NC. Это наблюдение называется сворачиванием NC-иерархии, потому что даже из одного равенстве в цепи вложений:

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

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

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

Ветвящаяся программа с переменными, шириной и длиной состоит из последовательности инструкций длины . Каждая инструкция — это тройка , где  — это индекс переменной, которую нужно проверить , а и  — это функции перестановки из в . Числа называются состояниями ветвящейся программы. Программа начинается в состоянии 1, и каждая инструкция изменяет состояние в или , в зависимости от того, равна ли -ая переменная 0 или 1.

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

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

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

Теорема Баррингтона[11] утверждает, что BWBP — это в точности нераспределенный NC1. Доказательство теоремы использует неразрешимость группы симметрии .[10]

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

Докажем, что ветвящаяся программа (ВП) с константной шириной и полиномиальным размером может быть превращена в схему из 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.

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

Примечания

  1. "Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27" (англ.). Архивировано 10 марта 2022. Дата обращения: 19 апреля 2020. {{cite journal}}: Cite journal требует |journal= ()
  2. Cook, Stephen A. (1985-01-01). "A taxonomy of problems with fast parallel algorithms". Information and Control. International Conference on Foundations of Computation Theory (англ.). 64 (1): 2—22. doi:10.1016/S0019-9958(85)80041-3. ISSN 0019-9958.
  3. Pippenger, Nicholas (1979). "On simultaneous resource bounds". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979) (англ.): 307—311. doi:10.1109/SFCS.1979.29. ISSN 0272-5428.
  4. Arora & Barak (2009) p.120
  5. 1 2 3 Arora & Barak (2009) p.118
  6. Papadimitriou (1994) Theorem 16.1
  7. 1 2 Clote & Kranakis (2002) p.437
  8. Clote & Kranakis (2002) p.12
  9. S. Bellantoni and I. Oitavem (2004). "Separating NC along the delta axis". Theoretical Computer Science. 318 (1—2): 57—78. doi:10.1016/j.tcs.2003.10.021.
  10. 1 2 Clote & Kranakis (2002) p.50
  11. Barrington, David A. (1989). "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1" (PDF). J. Comput. Syst. Sci. 38 (1): 150—164. doi:10.1016/0022-0000(89)90037-8. ISSN 0022-0000. Zbl 0667.68059.

Ссылки