Класс NC¶

Класс NC (от англ. Nick’s Class или Nondeterministic Circuit complexity) — это класс сложности в теории алгоритмов, включающий в себя задачи, которые могут быть решены за полилогарифмическое время (то есть время, пропорциональное (log n)^O(1)) на параллельном компьютере с полиномиальным числом процессоров. Формально, NC — это класс задач, разрешимых с помощью схем из функциональных элементов (булевых схем) полиномиального размера и полилогарифмической глубины, при условии, что каждый элемент схемы имеет ограниченное число входов (обычно два). Класс NC является одним из центральных понятий теории параллельных вычислений и тесно связан с вопросами эффективной распараллеливаемости алгоритмов.

¶Определение и формальное описание

Класс NC определяется как объединение классов NC^k для всех k ≥ 1, где NC^k — это класс задач, разрешимых с помощью семейства булевых схем {C_n} (n — длина входа) полиномиального размера (то есть число элементов в схеме не превосходит p(n) для некоторого полинома p) и глубины O((log n)^k). При этом каждый элемент схемы (логический вентиль) имеет не более двух входов, что соответствует ограничению на степень ветвления. Схемы должны быть однородными (uniform): существует детерминированная машина Тьюринга, которая по входу n за полиномиальное время строит схему C_n.

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

¶История

Понятие класса NC было введено в 1970-х годах американским математиком и специалистом по теории сложности Ником Пиппенджером (Nick Pippenger) в контексте изучения параллельных алгоритмов. Первоначально термин «NC» расшифровывался как «Nick’s Class» в честь Пиппенджера, хотя позже укоренилась и альтернативная расшифровка — «Nondeterministic Circuit complexity». В 1979 году Стивен Кук (Stephen Cook) в своей знаменитой работе «A taxonomy of problems with fast parallel algorithms» формализовал класс NC и установил его связь с классами P и LOGSPACE. Развитие теории параллельных вычислений в 1980-х годах, связанное с появлением машин с массовым параллелизмом (например, Connection Machine), стимулировало дальнейшие исследования NC.

¶Связь с другими классами сложности

Класс NC занимает важное место в иерархии классов сложности. Основные соотношения:

NC ⊆ P: любая задача, разрешимая за полилогарифмическое время на параллельной машине, может быть решена за полиномиальное время на последовательной машине (путём симуляции параллельных вычислений). Это тривиальное включение, так как полиномиальное число процессоров, работающих полилогарифмическое время, даёт общее время O(poly(n) * log^k n) = poly(n).
NC ⊆ PSPACE: очевидно, так как P ⊆ PSPACE.
NC ⊊ P?: вопрос о том, является ли включение NC в P строгим, остаётся открытой проблемой. Если NC = P, то это означало бы, что любую задачу, решаемую за полиномиальное время на последовательной машине, можно эффективно распараллелить. Однако общепринято считать, что NC ≠ P, так как существуют P-полные задачи (см. ниже), которые, вероятно, не принадлежат NC.
NC ⊆ AC: класс AC (схемы с неограниченной степенью ветвления) включает NC, так как схемы с ограниченным числом входов (NC) являются частным случаем схем с неограниченным числом входов (AC). Однако обратное неверно: AC содержит задачи, не входящие в NC, например, задача PARITY (проверка чётности числа единиц) не принадлежит NC^0, но принадлежит AC^0.
NC ⊆ LOGCFL: класс LOGCFL (задачи, сводимые к контекстно-свободным языкам с логарифмической памятью) включает NC, но не совпадает с ним.

¶P-полные задачи и проблема NC ≠ P

P-полные задачи — это задачи, которые принадлежат классу P и к которым любая другая задача из P может быть сведена с помощью логарифмического пространства (или полиномиального времени). Если какая-либо P-полная задача окажется в NC, то NC = P. Примеры P-полных задач:

Задача о достижимости в ориентированном графе (Circuit Value Problem): по заданной булевой схеме и входным значениям определить выход схемы.
Линейное программирование: поиск решения системы линейных неравенств.
Максимальный поток в сети (в некоторых формулировках).
Поиск в глубину (DFS) в графе.

Большинство исследователей полагают, что P-полные задачи не принадлежат NC, что обосновывается интуитивным представлением о том, что некоторые задачи по своей природе последовательны (например, вычисление значения схемы требует последовательного прохождения уровней). Однако строгого доказательства NC ≠ P не существует.

¶Примеры задач, принадлежащих NC

Ряд важных задач имеет эффективные параллельные алгоритмы и, следовательно, входит в NC:

Сложение и умножение n-битных чисел — классические алгоритмы (например, схема Кэрри-Лукаса для сложения) имеют глубину O(log n).
Умножение матриц — алгоритм Штрассена (с глубиной O(log n) при использовании параллельной версии).
Сортировка — параллельные алгоритмы сортировки (например, сортировка слиянием на параллельной машине) имеют глубину O(log^2 n).
Вычисление определителя матрицы — алгоритм Чистякова (Csanky) для определителя над полем характеристики 0 имеет глубину O(log^2 n).
Поиск наибольшего общего делителя (НОД) — параллельный алгоритм Шёнхаге.
Транзитивное замыкание графа — алгоритм на основе быстрого умножения матриц (глубина O(log^2 n)).

¶Классы внутри NC

Внутри NC выделяют подклассы в зависимости от степени полилогарифма глубины:

NC^0: схемы постоянной глубины (глубина O(1)). Задачи, решаемые с помощью схем с ограниченным числом уровней. Пример — вычисление функции XOR от двух переменных.
NC^1: глубина O(log n). Включает задачи, решаемые с помощью схем с логарифмической глубиной, например, сложение двух чисел.
NC^2: глубина O((log n)^2). Включает умножение матриц и сортировку.
NC^k: глубина O((log n)^k) для любого фиксированного k.

Существует иерархия: NC^0 ⊊ NC^1 ⊊ NC^2 ⊊ ... ⊊ NC. Строгость этих включений (кроме NC^0 ⊊ NC^1) не доказана, но предполагается.

¶Применение и значение

Класс NC имеет фундаментальное значение для теории параллельных вычислений и проектирования алгоритмов. Он позволяет формально определить, какие задачи могут быть эффективно распараллелены, а какие — нет. На практике алгоритмы из NC используются при разработке параллельных вычислительных систем (например, GPU, многопроцессорные системы) и в задачах, требующих высокой производительности (обработка больших данных, численное моделирование, криптография). Кроме того, изучение NC стимулировало развитие теории схемной сложности и методов построения эффективных параллельных алгоритмов, таких как метод «разделяй и властвуй» в параллельной версии.

¶Критика и ограничения

Несмотря на теоретическую значимость, класс NC имеет ряд ограничений. Во-первых, полилогарифмическая глубина схемы не всегда гарантирует практическую эффективность: константы в оценках могут быть большими, а число процессоров — экспоненциальным. Во-вторых, многие задачи, важные для приложений (например, решение систем линейных уравнений над полем вещественных чисел), не входят в NC из-за проблем с численной устойчивостью. В-третьих, класс NC не учитывает ограничения на память и коммуникацию между процессорами, что критично для реальных параллельных систем.

¶Источники

Cook, S. A. (1979). A taxonomy of problems with fast parallel algorithms. Information and Control, 43(1), 2–22.
Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley.
Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
Greenlaw, R., Hoover, H. J., & Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press.

Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru