НК (сложность)

В теории вычислительной сложности класс NC (от «Класса Ника») представляет собой набор задач решения, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача находится в NC , если существуют константы c и k такие, что ее можно решить за время O (log c  n ) с использованием 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.

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