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

редактировать

Нерешенная проблема в информатике :.

N C =? P {\ displaystyle {\ mathsf {NC}} {\ overset {?} {=}} {\ Mathsf {P}}}

{\ displaystyle {\ mathsf {NC}} { \ overset {?} {=}} {\ mathsf {P}}}

(другие нерешенные проблемы в информатике)

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

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

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

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

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

Содержание

1 Проблемы в NC
2 Иерархия NC
- 2.1 Открытая проблема: правильно ли NC?
3 Теорема Баррингтона
- 3.1 Доказательство теоремы Баррингтона
4 Примечания
5 Ссылки

Проблемы в NC

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

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

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

. Иерархия ЧПУ

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

NC 1 ⊆ NC 2 ⊆ ⋯ ⊆ NC i ⊆ ⋯ NC {\ displaystyle {\ mathsf {NC}} ^ {1} \ substeq {\ mathsf {NC}} ^ {2} \ substeq \ cdots \ substeq {\ mathsf {NC}} ^ {i} \ substeq \ cdots {\ mathsf {NC}}}

{\ displaystyle {\ mathsf {NC}} ^ {1} \ substeq {\ mathsf {NC}} ^ {2} \ substeq \ cdots \ substeq {\ mathsf {NC}} ^ {i} \ substeq \ cdots {\ mathsf {NC}}}

, которая формирует NC -иерархию.

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

N C 1 ⊆ L ⊆ N L ⊆ A C 1 ⊆ N C 2 ⊆ P. {\ Displaystyle {\ mathsf {NC}} ^ {1} \ substeq {\ mathsf {L}} \ substeq {\ mathsf {NL}} \ substeq {\ mathsf {AC}} ^ {1} \ substeq {\ mathsf {NC}} ^ {2} \ substeq {\ mathsf {P}}.}

{\ displaystyle {\ mathsf {NC}} ^ {1} \ substeq {\ mathsf {L}} \ substeq {\ mathsf {NL}} \ substeq {\ mathsf {AC}} ^ {1} \ substeq {\ mathsf {NC}} ^ { 2} \ substeq {\ mathsf {P}}.}

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

N C i ⊆ A C i ⊆ N C i + 1. {\ displaystyle {\ mathsf {NC}} ^ {i} \ substeq {\ mathsf {AC}} ^ {i} \ substeq {\ mathsf {NC}} ^ {i + 1}.}

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

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

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

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

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

NC 1 ⊆ NC 2 ⊆ ⋯ {\ displaystyle {\ mathsf {NC}} ^ {1} \ Substeq {\ mathsf {NC}} ^ {2} \ substeq \ cdots}

{\ displaystyle {\ mathsf {NC}} ^ {1} \ substeq {\ mathsf {NC}} ^ {2} \ substeq \ cdots}

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

$NC 1 ⊂ ⋯ ⊂ NC i ⊂ ⋯ ⊂ NC i + j ⊂ ⋯ NC {\ displaystyle {\ mathsf {NC}} ^ {1} \ subset \ cdots \ subset {\ mathsf {NC}} ^ {i} \ subset \ cdots \ subset {\ mathsf {NC}} ^ {i + j} \ subset \ cdots {\ mathsf {NC}}}$ ${\ displaystyle {\ mathsf {NC}} ^ {1} \ subset \ cdots \ subset {\ mathsf {NC}} ^ {i} \ subset \ cdots \ subset {\ mathsf {NC}} ^ {i + j} \ subset \ cdots {\ mathsf {NC}}}$
$NC 1 ⊂ ⋯ ⊂ NC i = ⋯ = NC я + J = ⋯ NC {\ Displaystyle {\ mathsf {NC}} ^ {1} \ subset \ cdots \ subset {\ mathsf {NC}} ^ {i} = \ cdots = {\ mathsf {NC} } ^ {i + j} = \ cdots {\ mathsf {NC}}}$ ${\ displaystyle {\ mathsf {NC}} ^ {1} \ subset \ cdots \ subset {\ mathsf {NC}} ^ {i} = \ cdots = {\ mathsf {NC}} ^ {i + j} = \ cdots {\ mathsf {NC}}}$

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

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

A программа ветвления с 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 обозначает класс языков, распознаваемых семейством ветвящихся программ ограниченной ширины и полиномиальной длины.

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

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

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

Программа ветвления постоянной ширины и полиномиального размера может быть легко преобразована (с помощью «разделяй и властвуй») в схему в 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, которая принимает входные данные x 1,..., 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 5, мы показали, что C также обладает этим свойством, как и требуется.

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

Примечания

Ссылки

Арора, Санджив ; Варак, Вооз (2009). Вычислительная сложность. Современный подход. Издательство Кембриджского университета. ISBN 978-0-521-42426-4. Zbl 1193.68112.
Клот, Петр; Кранакис, Эвангелос (2002). Булевы функции и вычислительные модели. Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
Гринлоу, Раймонд, Джеймс Гувер и Уолтер Руццо. Ограничения до параллельных вычислений; Теория P-полноты. ISBN 0-19-508591-4
Kozen, Dexter C. (1992). Разработка и анализ алгоритмов. Лекции 28 - 34 и 36
Kozen, Dexter C. (2006). Теория вычислений. Тексты по информатике. Спрингер-Верлаг. 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.