Введение

В теории вычислительной сложности класс NC (от "класс Ника") — это множество задач принятия решений, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Иными словами, задача с размером входа n принадлежит классу NC, если существуют константы c и k, такие что её можно решить за время O(log^k n) с использованием полиномиального числа параллельных процессоров. Стивен Кук назвал этот класс "классом Ника" в честь Ника Пиппенгера, который провёл обширные исследования схем с полилогарифмической глубиной и полиномиальным размером. Подобно тому, как класс P можно рассматривать как класс разрешимых задач (тезис Кобэма), класс NC можно рассматривать как задачи, которые могут быть эффективно решены на параллельном компьютере. NC является подмножеством P, поскольку полилогарифмические параллельные вычисления могут быть смоделированы последовательными вычислениями за полиномиальное время. Неизвестно, верно ли, что NC = P, но большинство исследователей полагают, что это не так, то есть, вероятно, существуют некоторые разрешимые задачи, которые являются "по своей сути последовательными" и не могут быть существенно ускорены за счёт использования параллелизма. Подобно тому, как класс NP-полных задач можно рассматривать как "вероятно неразрешимые", класс P-полных задач, при использовании NC-сводимостей, можно рассматривать как "вероятно непараллелизуемые" или "вероятно, по своей сути последовательные". Параллельный компьютер в определении можно считать машиной с параллельным произвольным доступом к памяти (PRAM). Это параллельный компьютер с центральным пулом памяти, и любой процессор может получить доступ к любому биту памяти за постоянное время. Определение NC не зависит от способа обработки PRAM при одновременном доступе к одному биту несколькими процессорами. Это может быть CRCW, CREW или EREW. Подробное описание этих моделей можно найти в статье PRAM. Эквивалентно, NC можно определить как множество задач принятия решений, разрешимых с помощью однородной булевой схемы (которая может быть вычислена на основе длины входа; для NC мы предполагаем, что булеву схему размера n можно вычислить в логарифмическом пространстве по n) с полилогарифмической глубиной и полиномиальным числом вентилей с максимальным числом входов 2. RNC — это класс, расширяющий NC с доступом к случайности.

Пример

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

Иерархия НК

NCi — это класс задач принятия решений, разрешимых с помощью однородных булевых схем с полиномиальным числом ворот, имеющих не более двух входов и глубину O((log n)^i), или класс задач принятия решений, разрешаемых за время O((log n)^i) на параллельном компьютере с полиномиальным числом процессоров. Очевидно, это формирует иерархию NC. Мы можем соотнести классы NC с классами пространства L и NL, а также с классом AC. Классы NC связаны с классами AC, которые определены аналогично, но с воротами, имеющими неограниченное количество входов. Для каждого i справедливо, что оба включения строги при i = 0.

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

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

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

NC0

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

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

Программа ветвления с 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. Семейство программ ветвления состоит из программы ветвления с n переменными для каждого n. Оно принимает язык, когда программа с n переменными принимает язык, ограниченный входами длины n. Легко показать, что любой язык L над {0,1} может быть распознан семейством программ ветвления ширины 5 и экспоненциальной длины, или семейством экспоненциальной ширины и линейной длины. Любой регулярный язык над {0,1} может быть распознан семейством программ ветвления постоянной ширины и линейным числом инструкций (поскольку ДКА может быть преобразован в программу ветвления). BWBP обозначает класс языков, распознаваемых семейством программ ветвления ограниченной ширины и полиномиальной длины. Теорема Баррингтона утверждает, что BWBP совпадает с неравномерным NC1. В доказательстве используется неразрешимость задачи для симметрической группы S5. Теорема довольно удивительна. Например, она подразумевает, что функцию большинства можно вычислить с помощью семейства программ ветвления постоянной ширины и полиномиального размера, в то время как интуиция может подсказать, что для достижения полиномиального размера требуется линейное число состояний.

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

Программа ветвления постоянной ширины и полиномиального размера может быть легко преобразована (методом "разделяй и властвуй") в схему в NC1. И наоборот, предположим, что дана схема в NC1. Без потери общности, предположим, что она использует только логические элементы И и НЕ. Назовем программой ветвления α вычисляющей схему C, если она действует как функция идентичности при выходном значении 0, и как при выходном значении 1. Как следствие леммы 1 и того факта, что все циклы длины 5 сопряжены, для любых двух циклов 5 , , если существует программа ветвления α, вычисляющая схему C, то существует программа ветвления β, вычисляющая схему C, той же длины. Размер программы ветвления не превышает 4, где d – глубина схемы. Если глубина схемы логарифмическая, то программа ветвления имеет полиномиальную длину.