Класс NC
В теории сложности вычислений классом NC (от англ. Nick’s Class) называют множество задач разрешимости, разрешимых за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров. Другими словами, задача принадлежит классу NC, если существуют константы и такие, что она может быть решена за время при использовании параллельных процессоров. Стивен Кук[1][2] назвал его «Классом Ника» в честь Ника Пиппенжера[англ.], который провел обширные исследования[3] схем с полилогарифмической глубиной и полиномиальным размером.[4]
Так же, как класс P можно считать классом податливых задач (Тезис Кобхэма[англ.]), так и NC можно считать классом задач, которые могут быть эффективно решены на параллельном компьютере.[5] NC — это подмножество P, потому что параллельные полилогарифмические вычисления можно симулировать с помощью последовательных полиномиальных вычислений. Неизвестно, верно ли NP = P, но большинство ученых считает, что нет, из чего следует, что скорее всего существуют податливые задачи, которые последовательны «от природы», и не могут быть существенно ускорены при использовании параллелизма. Так же, как класс NP-полных задач можно считать классом «скорее всего неподатливых» задач, так и класс P-полных задач, при сведении к NC, можно считать «скорее всего не параллелизуемым» или «скорее всего последовательным от природы».
Параллельный компьютер в определении можно считать параллельной машиной с произвольным доступом (PRAM — от англ. parallel, random-access machine). Это параллельный компьютер с центральным пулом памяти, любой процессор которого может получить доступ к любому биту за константное время. На определение NC не влияет способ, с помощью которого PRAM осуществляет одновременный доступ нескольких процессоров к одному биту.
NC может быть определён, как множество задач разрешимости, разрешимых распределённой Булевой схемой с полилогарифмической глубиной и полиномиальным числом вентилей.
Задачи в NC
NC включает в себя много задач, в том числе:
- Сложение, умножение и деление целых чисел;
- Умножение матриц, подсчет их ранга, детерминанта, обратной матрицы;
- Полиномиальный НОД;
- Нахождение максимального паросочетания.
Часто алгоритмы для этих задач придумывались отдельно и не могли быть наивной адаптацией известных алгоритмов — Метод Гаусса и алгоритм Евклида полагаются на то, что операции выполняются последовательно.
Иерархия NC
NCi — это множество задач разрешимости, разрешимых распределенными булевыми схемами с полиномиальным количеством вентилей (с количеством входов, не большим двух) и глубиной , или разрешимых за время параллельным компьютером с полиномиальным числом процессоров. Очевидно,
что представляет собой NC-иерархию.
Мы можем связать классы NC с классами памяти L, NL[6] и AC[7]:
Классы NC и AC одинаково определены, за исключением неограниченности количества входов у вентилей для класса AC. Для каждого верно[5][7]:
Следствием этого является NC = AC.[8] Известно, что оба включения строгие для .[5] Похожим образом можем получить, что NC эквивалентен множеству задач, решаемых на переменной машине Тьюринга с числом выборов на каждом шаге не большим, чем двух, и с O(log n) памяти и альтерациями.[9]
Нерешенная задача: является ли NC собственным?
Один из больших открытых вопросов теории сложности вычислений — является ли собственным каждое вложение NC-иерархии. Как было замечено Пападимитриу, если для какого-то верно NCi = NCi+1, то NCi = NCj для всех , и как следствие, NCi = NC. Это наблюдение называется сворачиванием NC-иерархии, потому что даже из одного равенстве в цепи вложений:
следует, что вся NC-иерархия «сворачивается» до какого-то уровня . Таким образом, возможны два варианта:
Широко распространено мнение, что верно именно (1), хотя пока не обнаружено никаких доказательств в отношении истинности того или иного утверждения.
Теорема Баррингтона
Ветвящаяся программа с переменными, шириной и длиной состоит из последовательности инструкций длины . Каждая инструкция — это тройка , где — это индекс переменной, которую нужно проверить , а и — это функции перестановки из в . Числа называются состояниями ветвящейся программы. Программа начинается в состоянии 1, и каждая инструкция изменяет состояние в или , в зависимости от того, равна ли -ая переменная 0 или 1.
Семейство ветвящихся программ состоит из ветвящихся программ с переменными для каждого .
Легко показать, что любой язык на может быть распознан семейством ветвящихся программ с шириной 5 и экспоненциальной длиной, или семейством с экспоненциальной шириной и линейной длиной.
Каждый регулярный язык на может быть распознан семейством ветвящихся программ с константной шириной и линейным числом инструкций (так как ДКА может быть преобразован в ветвящуюся программу). BWBP обозначает класс языков, распознаваемых семейством ветвящихся программ с ограниченной шириной и полиномиальной длиной (англ BWBP — bounded width and polynomial length).[10].
Теорема Баррингтона[11] утверждает, что BWBP — это в точности нераспределенный NC1. Доказательство теоремы использует неразрешимость группы симметрии .[10]
Доказательство теоремы Баррингтона
Докажем, что ветвящаяся программа (ВП) с константной шириной и полиномиальным размером может быть превращена в схему из NC1.
От противного: пусть есть схема C из NC1. Без ограничения общности, будем считать что в ней используются только вентили И и НЕ.
Определение: ВП называется -вычисляющей булеву функцию или , если при она дает результат — тождественную перестановку, а при её результат — -перестановка. Так как наша схема C описывает какую-то булеву функцию и только её, можем взаимно заменять эти термины.
Для доказательства будем использовать две леммы:
Лемма 1: Если есть ВП, -вычисляющая , то существует и ВП, -вычисляющая (то есть, равная при , и равная при .
Доказательство: так как и — циклы, а любые два цикла являются сопряженными, то существует такая перестановка , что = . Тогда домножим на перестановки и из первой инструкции ВП слева (чтобы получить перестановки и ), а перестановки из последней инструкции домножим на справа (получим и ). Если до наших действий (без ограничения общности) был равен , то теперь результат будет , а если был равен , то результат равен . Так, мы получили ВП, -вычисляющую , с той же длиной (количество инструкций не поменялось).
Примечание: если домножить вывод ВП на справа, то очевидным образом получим ВП, -вычисляющую функцию .
Лемма 2: Если есть два ВП: -вычисляющая и -вычисляющая с длинами и , где и — 5-цикличные перестановки, то существует ВП с 5-цикличной перестановкой такая, что ВП -вычисляет, и её размер не превосходит + .
Доказательство: Выложим «в ряд» инструкции четырёх ВП: , , , (строим обратные по лемме 1). Если одна или обе функции выдают 0, то результат большой программы : например, при . Если обе функции выдают 1, то . Здесь , что верно из-за того, что эти перестановки 5-цикличны (из-за неразрешимости группы симметрии ). Длина новой ВП высчитывается по определению.
Доказательство теоремы
Будем доказывать по индукции. Предположим, что у нас есть схема C с входами и что для всех подсхем D и 5-цикличных перестановок существует ВП, -вычисляющая D. Покажем, что для всех 5-перестановок существует ВП, -вычисляющий C.
- Если схема C выдает , то ВП имеет одну инструкцию: проверить значение (0 или 1), и отдать или (соответственно).
- Если схема C выдает A для какой-то другой схемы A, по примечанию к лемме 1 создадим ВП, -вычисляющую A.
- Если схема C выдает AB для схем A и B, создадим нужную ВП по лемме 2.
Размер итоговой ветвящейся программы не превосходит , где — это глубина схемы. Если у схемы логарифмическая глубина, то у ВП полиномиальная длина.
Примечания
- ↑ "Towards a complexity theory of synchronous parallel computation. D L'Enseignement mathematique 27" (англ.). Архивировано 10 марта 2022. Дата обращения: 19 апреля 2020.
{{cite journal}}
: Cite journal требует|journal=
(справка) - ↑ Cook, Stephen A. (1985-01-01). "A taxonomy of problems with fast parallel algorithms". Information and Control. International Conference on Foundations of Computation Theory (англ.). 64 (1): 2—22. doi:10.1016/S0019-9958(85)80041-3. ISSN 0019-9958.
- ↑ Pippenger, Nicholas (1979). "On simultaneous resource bounds". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979) (англ.): 307—311. doi:10.1109/SFCS.1979.29. ISSN 0272-5428.
- ↑ Arora & Barak (2009) p.120
- ↑ 1 2 3 Arora & Barak (2009) p.118
- ↑ Papadimitriou (1994) Theorem 16.1
- ↑ 1 2 Clote & Kranakis (2002) p.437
- ↑ Clote & Kranakis (2002) p.12
- ↑ S. Bellantoni and I. Oitavem (2004). "Separating NC along the delta axis". Theoretical Computer Science. 318 (1—2): 57—78. doi:10.1016/j.tcs.2003.10.021.
- ↑ 1 2 Clote & Kranakis (2002) p.50
- ↑ Barrington, David A. (1989). "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1" (PDF). J. Comput. Syst. Sci. 38 (1): 150—164. doi:10.1016/0022-0000(89)90037-8. ISSN 0022-0000. Zbl 0667.68059.
Ссылки
- Arora, Sanjeev. Computational complexity. A modern approach / Sanjeev Arora, Boaz Barak. — Cambridge University Press, 2009. — ISBN 978-0-521-42426-4.
- Clote, Peter. Boolean functions and computation models / Peter Clote, Evangelos Kranakis. — Berlin : Springer-Verlag, 2002. — ISBN 3-540-59436-1.
- Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. Архивная копия от 4 июня 2013 на Wayback Machine ISBN 0-19-508591-4
- Kozen, Dexter C. The design and analysis of algorithms. — 1992. Lectures 28 — 34 and 36
- Kozen, Dexter C. Theory of Computation. — Springer-Verlag, 2006. — ISBN 1-84628-297-7. Lecture 12: Relation of NC to Time-Space Classes
- Papadimitriou, Christos. Section 15.3: The class NC // Computational Complexity. — 1st. — Addison Wesley, 1993. — P. 375–381. — ISBN 0-201-53082-1.
- Straubing, Howard. Finite automata, formal logic, and circuit complexity. — Basel : Birkhäuser, 1994. — ISBN 3-7643-3719-2.
- Vollmer, Heribert. Introduction to circuit complexity. A uniform approach. — Berlin : Springer-Verlag, 1998. — ISBN 3-540-64310-9.