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

Нерешенная проблема в информатике: ${displaystyle {mathsf {NC}}{overset {?}{=}}{mathsf {P}}}$ (больше нерешенных проблем в информатике)

В теория сложности вычислений, класс NC (для «Класса Ника») - это набор проблемы решения разрешимый в полилогарифмическое время на параллельный компьютер с полиномиальным количеством процессоров. Другими словами, проблема в NC если существуют константы c и k так что это может быть решено вовремя О (бревно^c п) с помощью О (п^k) параллельные процессоры. Стивен Кук^[1][2] придумал название "класс Ника" после Ник Пиппенгер, который провел обширное исследование^[3] на схемах с полилогарифмической глубиной и полиномиальным размером.^[4]

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

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

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

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

Проблемы в NC

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

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

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

Иерархия ЧПУ

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

${displaystyle {mathsf {NC}}^{1}subseteq {mathsf {NC}}^{2}subseteq cdots subseteq {mathsf {NC}}^{i}subseteq 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, которые определены аналогично, но с элементами, имеющими неограниченное разветвление. Для каждого я, у нас есть^[5][7]

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

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

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

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

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

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

означает, что весь NC иерархия "рушится" до некоторого уровня я. Таким образом, есть 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⁰ работает только с постоянной длиной входных битов. Поэтому он описывается как класс функций, определяемых однородными логическими схемами с постоянной глубиной и ограниченным разветвлением.

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

А программа ветвления с п переменные ширины k и длина м состоит из последовательности м инструкции. Каждая инструкция представляет собой кортеж (я, п, q) куда я индекс проверяемой переменной (1 ≤ я ≤ п), и п и q - функции из {1, 2, ..., k} на {1, 2, ..., k}. Числа 1, 2, ..., k называются состояниями ветвящейся программы. Программа изначально запускается в состоянии 1, и каждая инструкция (я, п, q) меняет состояние с Икс к п(Икс) или же q(Икс), в зависимости от того, я-я переменная равна 0 или 1.

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

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

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

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

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

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

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

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

Лемма 1. Если существует программа ветвления, которая иногда работает как перестановка п а иногда как перестановка Q, умножая правые перестановки в первой инструкции на α, а в последней инструкции умножая слева на β, мы можем создать схему той же длины, которая ведет себя как βпα или β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.

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

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

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

Примечания

1. «К теории сложности синхронных параллельных вычислений. D L'Enseignement mathematique 27».
2. Кук, Стивен А. (1 января 1985 г.). «Таксономия проблем с быстрыми параллельными алгоритмами». Информация и контроль. Международная конференция по основам теории вычислений. 64 (1): 2–22. Дои:10.1016 / S0019-9958 (85) 80041-3. ISSN  0019-9958.
3. Пиппенгер, Николас (1979). «На границах одновременных ресурсов». 20-й ежегодный симпозиум по основам компьютерных наук (SFCS 1979): 307–311. Дои:10.1109 / SFCS.1979.29. ISSN  0272-5428.
4. Арора и Барак (2009) с.120
5. Арора и Барак (2009) с.118
6. Пападимитриу (1994) Теорема 16.1.
7. Клот и Кранакис (2002) стр. 437
8. Клот и Кранакис (2002) стр.12
9. С. Беллантони и И. Оитавем (2004). «Разделение ЧПУ по дельта-оси». Теоретическая информатика. 318 (1–2): 57–78. Дои:10.1016 / j.tcs.2003.10.021.
10. Клот и Кранакис (2002) стр.50
11. Баррингтон, Дэвид А. (1989). "Программы ветвления полиномиального размера ограниченной ширины распознают именно эти языки в NC¹" (PDF). J. Comput. Syst. Наука. 38 (1): 150–164. Дои:10.1016/0022-0000(89)90037-8. ISSN  0022-0000. Zbl  0667.68059.

Рекомендации

• Арора, Санджив; Варак, Вооз (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.