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

Нерешенная задача в информатике :

⁠ ${\mathsf {NC}}{\overset {?}{=}}{\mathsf {P}}$⁠

(еще нерешенные проблемы по информатике)

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

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

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

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

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

Проблемы в НК

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

• Целочисленное сложение, умножение и деление;
• Умножение матрицы , определитель, обратная , ранг;
• Полиномиальный НОД путем сведения к линейной алгебре с использованием матрицы Сильвестра.
• Нахождение максимального паросочетания.

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

Пример

Пример проблемы в NC ¹ — это проверка четности битовой строки. Задача состоит в подсчете количества единиц в строке, состоящей из 1 и 0. Простое решение состоит в суммировании всех битов строки. Поскольку сложение ассоциативно, $x_{1}+\cdots +x_{n}=(x_{1}+\cdots +x_{\frac {n}{2}})+(x_{{\frac {n}{2}}+1}+\cdots +x_{n})$. Рекурсивно применяя такое свойство, можно построить двоичное дерево длины $O(log(n))$ в котором каждая сумма между двумя битами $x_{i}$ и $x_{j}$ выражается посредством основных логических операторов , например, посредством логического выражения $(x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})$.

Иерархия NC

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

${\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}}$

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

Мы можем связать классы NC с пространственными классами L и NL. и АС .

${\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.$

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

${\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.$

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

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

Открытая проблема: подходит ли NC?

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

${\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots$

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

1. ${\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}$
2. ${\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}$

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

Северная Каролина ⁰

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

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

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

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

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

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

Теорема Баррингтона говорит, что BWBP является в точности неоднородным NC ¹ . Доказательство использует неразрешимость симметрической группы S ₅ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

• Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность. Современный подход . Издательство Кембриджского университета . ISBN  978-0-521-42426-4 . Збл   1193.68112 .
• Клот, Питер; Кранакис, Евангелос (2002). Булевы функции и модели вычислений . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN  3-540-59436-1 . Артикул   1016.94046 .
• Гринлоу, Рэймонд, Джеймс Гувер и Уолтер Руццо. Ограничения параллельных вычислений; Теория P-полноты . ISBN   0-19-508591-4
• Козен, Декстер К. (1992). Проектирование и анализ алгоритмов . Лекции 28–34 и 36
• Козен, Декстер К. (2006). Теория вычислений . Тексты по информатике. Издательство Спрингер . ISBN  1-84628-297-7 . Збл   1102.68025 . Лекция 12: Связь NC с классами пространства-времени
• Пападимитриу, Христос (1993). «Раздел 15.3: Класс NC ». Вычислительная сложность (1-е изд.). Эддисон Уэсли. стр. 375–381. ISBN  0-201-53082-1 .
• Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы . Прогресс в теоретической информатике. Базель: Биркхойзер. ISBN  3-7643-3719-2 . Заказ №   0816.68086 .
• Воллмер, Гериберт (1998). Введение в сложность схемы. Единый подход . Тексты по теоретической информатике. Берлин: Springer-Verlag . ISBN  3-540-64310-9 . Збл   0931.68055 .