NC (сложность)
Класс по теории сложности вычислений
Нерешенная проблема в информатике :
⁠ ⁠ Н С = ? П {\displaystyle {\mathsf {NC}}{\overset {?}{=}}{\mathsf {P}}}
(еще нерешенные проблемы в информатике)

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

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

Параллельный компьютер в определении можно считать параллельной машиной с произвольным доступом ( PRAM ). Это параллельный компьютер с центральным пулом памяти, и любой процессор может получить доступ к любому биту памяти за постоянное время. Определение NC не зависит от выбора того, как PRAM обрабатывает одновременный доступ к одному биту более чем одним процессором. Это может быть CRCW, CREW или EREW. См. PRAM для описания этих моделей.

Эквивалентно, NC можно определить как те задачи принятия решений, которые разрешимы с помощью однородной булевой схемы (которую можно вычислить по длине входных данных; для NC мы предполагаем, что можем вычислить булеву схему размера n в логарифмическом пространстве за n ) с полилогарифмической глубиной и полиномиальным числом вентилей с максимальным коэффициентом объединения по входу, равным 2.

RNC — это класс, расширяющий NC с доступом к случайности.

Проблемы в Северной Каролине

Как и в случае с P , при небольшом злоупотреблении языком можно было бы классифицировать функциональные проблемы и проблемы поиска как относящиеся к NC . Известно, что NC включает в себя множество проблем, включая

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

Пример

Примером проблемы в NC 1 является проверка четности в строке битов. [6] Задача состоит в подсчете количества единиц в строке, состоящей из 1 и 0. Простое решение состоит в суммировании всех битов строки. Поскольку сложение ассоциативно, . Рекурсивно применяя это свойство, можно построить двоичное дерево длины , в котором каждая сумма между двумя битами и выражается с помощью базовых логических операторов , например, через булево выражение . х 1 + ⋯ + х н = ( х 1 + ⋯ + х н 2 ) + ( х н 2 + 1 + ⋯ + х н ) {\displaystyle x_{1}+\cdots +x_{n}=\left(x_{1}+\cdots +x_{\frac {n}{2}}\right)+\left(x_{{\frac {n}{2}}+1}+\cdots +x_{n}\right)} О ( бревно ⁡ ( н ) ) {\displaystyle O(\log(n))} х я {\displaystyle x_{i}} х дж {\displaystyle x_{j}} ( х я ∧ ¬ х дж ) ∨ ( ¬ х я ∧ х дж ) {\displaystyle (x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})}

Иерархия NC

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

Н С 1 ⊆ Н С 2 ⊆ ⋯ ⊆ Н С я ⊆ ⋯ Н С {\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}}}

что образует NC -иерархию.

Мы можем связать классы NC с классами пространств L и NL [7] и AC . [8]

Н С 1 ⊆ Л ⊆ Н Л ⊆ А С 1 ⊆ Н С 2 ⊆ П . {\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.}

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

Н С я ⊆ А С я ⊆ Н С я + 1 . {\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.}

Как непосредственное следствие этого, имеем, что NC = AC . [9] Известно, что оба включения строгие при i = 0. [5]

Аналогично, мы имеем, что NC эквивалентно задачам, решаемым на чередующейся машине Тьюринга, ограниченной максимум двумя вариантами на каждом шаге с O (log n ) пространства и чередованиями. [10] ( бревно ⁡ н ) О ( 1 ) {\displaystyle (\log n)^{O (1)}}

Открытая проблема: является ли NC правильным?

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

Н С 1 ⊆ Н С 2 ⊆ ⋯ {\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots }

подразумевает, что вся иерархия NC "схлопывается" до некоторого уровня i . Таким образом, есть 2 возможности:

  1. Н С 1 ⊂ ⋯ ⊂ Н С я ⊂ ⋯ ⊂ Н С я + дж ⊂ ⋯ Н С {\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}}
  2. Н С 1 ⊂ ⋯ ⊂ Н С я = ⋯ = Н С я + дж = ⋯ Н С {\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}}

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

NC0

Специальный класс NC 0 работает только с постоянной длиной входных битов. Поэтому он описывается как класс функций, определяемых однородными булевыми схемами с постоянной глубиной и ограниченным фан-входом.

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

Ветвящаяся программа с n переменными ширины k и длины m состоит из последовательности m инструкций. Каждая из инструкций представляет собой кортеж ( i , p , q ), где i — индекс проверяемой переменной (1 ≤ i ≤ n ), а p и q — функции от {1, 2, ..., k } до {1, 2, ..., k }. Числа 1, 2, ..., k называются состояниями ветвящейся программы. Программа изначально запускается в состоянии 1, и каждая инструкция ( i , p , q ) изменяет состояние с x на p ( x ) или q ( x ), в зависимости от того, равна ли i -я переменная 0 или 1. Функция, отображающая вход в конечное состояние программы, называется выходом программы (точнее, выход на входе — это функция, отображающая любое начальное состояние в соответствующее конечное состояние). Программа принимает набор значений переменных, когда существует некоторый набор функций, такой что последовательность переменных находится в A именно тогда , когда ее выход находится в F. А ⊂ 2 н {\displaystyle A\subset 2^{n}} Ф ⊂ к к {\displaystyle F\subset k^{k}} х ∈ 2 н {\displaystyle x\in 2^{n}}

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

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

Каждый регулярный язык на {0,1} может быть распознан семейством ветвящихся программ постоянной ширины и линейного числа инструкций (поскольку DFA может быть преобразован в ветвящуюся программу). BWBP обозначает класс языков, распознаваемых семейством ветвящихся программ ограниченной ширины и полиномиальной длины. [11]

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

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

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

Разветвленную программу постоянной ширины и полиномиального размера можно легко преобразовать (с помощью принципа «разделяй и властвуй») в схему в NC 1 .

Наоборот, предположим, что дана схема в NC 1. Без потери общности предположим, что она использует только вентили И и НЕ.

Лемма 1  —  Если существует разветвляющаяся программа, которая иногда работает как перестановка P , а иногда как перестановка Q , то, умножая перестановки в первой инструкции справа на α , а в последней инструкции умножая слева на β , мы можем создать схему той же длины, которая ведет себя как β P α или β Q α соответственно.

Назовем разветвленную программу α-вычислением схемы C, если она работает как тождество, когда выход C равен 0, и как α , когда выход C равен 1.

Как следствие леммы 1 и того факта, что все циклы длины 5 сопряжены , для любых двух 5-циклов α , β , если существует ветвящаяся программа, α-вычисляющая схему C , то существует ветвящаяся программа, β-вычисляющая схему C , той же длины.

Лемма 2.  Существуют  5-циклы γ , δ такие, что их коммутатор ε = γδγ −1 δ −1 является 5-циклом. Например, γ = (1 2 3 4 5), δ = (1 3 5 4 2), что дает ε = (1 3 2 5 4).

Доказательство

Теперь докажем теорему Баррингтона методом индукции:

Предположим, что у нас есть схема C , которая принимает входы x 1 ,..., x n и предположим, что для всех подсхем D схемы C и 5-циклов α существует ветвящаяся программа α-вычисления D. Мы покажем, что для всех 5-циклов α существует ветвящаяся программа α-вычисления C.

  • Если схема C просто выводит некоторый входной бит x i , то нужная нам программа ветвления имеет всего одну инструкцию: проверку значения x i (0 или 1) и вывод тождества или α (соответственно).
  • Если схема C выводит ¬ A для некоторой другой схемы A , создайте ветвящуюся программу α −1 -вычисляющую A , а затем умножьте вывод программы на α. По лемме 1 мы получаем ветвящуюся программу для A , выводящую тождество или α, т. е. α -вычисляющую ¬ A = C.
  • Если схема C выводит A ∧ B для схем A и B , объедините программы ветвления, которые γ -вычисляют A , δ -вычисляют B , γ −1 -вычисляют A и δ −1 -вычисляют B для выбора 5-циклов γ и δ таких, что их коммутатор ε = γδγ −1 δ −1 также является 5-циклом. (Существование таких элементов было установлено в Лемме 2.) Если одна или обе схемы выводят 0, результирующая программа будет тождественной из-за сокращения; если обе схемы выводят 1, результирующая программа выведет коммутатор ε . Другими словами, мы получаем программу ε -вычисляющую A ∧ B . Поскольку ε и α являются двумя 5-циклами, они сопряжены, и, следовательно, существует программа α -вычисления A ∧ B по лемме 1.

Предположив, что подсхемы имеют разветвленные программы, так что они являются α -вычислительными для всех 5-циклов α ∈ S 5 , мы показали, что C также обладает этим свойством, как и требовалось.

Размер программы ветвления не более 4 d , где d — глубина схемы. Если схема имеет логарифмическую глубину, программа ветвления имеет полиномиальную длину.

Примечания

  1. ^ Кук, С.А. (1981). «К теории сложности синхронных параллельных вычислений». L'Enseignement Mathématique . 27 : 99–124 . Архивировано из оригинала 10.03.2022.
  2. ^ Кук, Стивен А. (1985-01-01). "Таксономия проблем с быстрыми параллельными алгоритмами". Информация и управление . Международная конференция по основам теории вычислений. 64 (1): 2– 22. doi : 10.1016/S0019-9958(85)80041-3 . ISSN  0019-9958.
  3. ^ Пиппенджер, Николас (1979). «О границах одновременных ресурсов». 20-й ежегодный симпозиум по основам компьютерной науки (SFCS 1979) : 307–311 . doi :10.1109/SFCS.1979.29. ISSN  0272-5428. S2CID  7029313.
  4. ^ Арора и Барак (2009) стр.120
  5. ^ abc Арора и Барак (2009) стр.118
  6. ^ Дэвид Микс Баррингтон; Алексис Масиэль (2000-07-18). "Лекция 2: Сложность некоторых проблем" (PDF) . Летняя сессия IAS/PCMI 2000 г. - Программа бакалавриата по математике в Клэе - Базовый курс по вычислительной сложности . Университет Кларксона . Получено 11 ноября 2021 г.
  7. ^ Пападимитриу (1994) Теорема 16.1
  8. ^ ab Clote & Kranakis (2002) стр.437
  9. ^ Клот и Кранакис (2002) стр.12
  10. ^ S. Bellantoni и I. Oitavem (2004). «Разделение NC вдоль оси дельта». Теоретическая информатика . 318 ( 1– 2): 57– 78. doi :10.1016/j.tcs.2003.10.021.
  11. ^ ab Clote & Kranakis (2002) стр.50
  12. ^ Баррингтон, Дэвид А. (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.

Ссылки

Взято с "https://en.wikipedia.org/w/index.php?title=NC_(complexity)&oldid=1264025289"