NC (сложность)

В теории сложности вычислений класс 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.

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

Проблемы в NC [ править ]

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

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

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

Иерархия ЧПУ [ править ]

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

${\ Displaystyle {\ mathsf {NC}} ^ {1} \ substeq {\ mathsf {NC}} ^ {2} \ substeq \ cdots \ substeq {\ mathsf {NC}} ^ {i} \ substeq \ cdots {\ mathsf {NC}}}$

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

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

${\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] [7]}

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

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

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

Открытая проблема: ЧПУ правильное? [ редактировать ]

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

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

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

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

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

NC ⁰ [ править ]

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

Теорема Баррингтона [ править ]

Программа ветвления с 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметки [ править ]

Ссылки [ править ]

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