Сложность схемы

Пример логической схемы. Эти узлы вентилей И , как узлы ИЛИ ворота , а узлы НЕ ворота

{\ Displaystyle \ клин}

{\ displaystyle \ vee}

{\ displaystyle \ neg}

В теоретической информатике , схемные является ветвью теории сложности вычислений , в которой булевы функции классифицируются в зависимости от размера или глубин булевых схем , которые вычисляют их. Связанное с этим понятием является схема сложности рекурсивного языка , который решил с помощью единого семейства цепей (см ниже). ${\ Displaystyle C_ {1}, C_ {2}, \ ldots}$

Доказательство нижних границ размера булевых схем, вычисляющих явные булевы функции, является популярным подходом к разделению классов сложности. Например, известный класс схем P / poly состоит из булевых функций, вычисляемых схемами полиномиального размера. Доказательство того, что разделит P и NP (см. Ниже). ${\ Displaystyle {\ mathsf {NP}} \ not \ substeq {\ mathsf {P / poly}}}$

Классы сложности, определенные в терминах логических схем, включают AC ⁰ , AC , TC ⁰ , NC ¹ , NC и P / poly .

Размер и глубина

Булева схема с входными битами является ориентированным ациклическим графом , в котором каждый узел (обычно называемые ворота в данном контексте) является либо входным узлом в-степени 0 меченых одним из входных бит, с логическим элементом И , на логический элементе ИЛИ , или НЕ ворота . Один из этих ворот обозначается как выходной. Такая схема естественным образом вычисляет функцию своих входов. Размер схемы - это количество элементов, которые она содержит, а ее глубина - это максимальная длина пути от входного элемента до выходного элемента. ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n}$

Есть два основных понятия сложности схем ^[1] схема размера сложность булевой функции является минимальным размером любой схемы вычислений . Схема глубина сложность булевой функции является минимальной глубиной любой схемы вычислений . ${\ displaystyle f}$ ${\ displaystyle f}$ ${\ displaystyle f}$ ${\ displaystyle f}$

Эти понятия обобщаются, если рассматривать сложность схемы любого языка, который содержит строки с разной битовой длиной, особенно бесконечных формальных языков . Однако логические схемы допускают только фиксированное количество входных битов. Таким образом, ни одна логическая схема не способна определить такой язык. Чтобы учесть эту возможность, мы рассматриваем семейства схем, каждая из которых принимает входы определенного размера . Каждое семейство схем естественным образом генерирует язык путем вывода схемы, когда строка длины является членом семейства, и в противном случае. Мы говорим, что семейство схем имеет минимальный размер, если нет другого семейства, которое принимает решение о входах любого размера, ${\ Displaystyle C_ {1}, C_ {2}, \ ldots}$ ${\ displaystyle C_ {n}}$ ${\ displaystyle n}$ ${\ displaystyle C_ {n}}$ ${\ displaystyle 1}$ ${\ displaystyle n}$ ${\ displaystyle 0}$ ${\ displaystyle n}$ , со схемой меньшего размера (соответственно для семейств с минимальной глубиной ). Таким образом, сложность схемы имеет значение даже для нерекурсивных языков . Понятие однородного семейства позволяет связать варианты сложности схемы с мерами сложности рекурсивных языков, основанными на алгоритмах. Тем не менее, неоднородный вариант полезен для определения нижней границы того, насколько сложным должно быть любое семейство схем, чтобы выбрать данные языки. ${\ displaystyle C_ {n}}$

Следовательно, сложность размера схемы формального языка определяется как функция , которая связывает длину в битах ввода со сложностью размера схемы минимальной схемы, которая определяет, находятся ли входы такой длины в . Сложности схем глубины определяется аналогично. $A$ $t:\mathbb {N} \to \mathbb {N}$ $n$ $C_{n}$ $A$

Единообразие

Булевы схемы являются одним из ярких примеров так называемых неоднородных моделей вычислений в том смысле, что входные данные разной длины обрабатываются разными схемами, в отличие от унифицированных моделей, таких как машины Тьюринга, где одно и то же вычислительное устройство используется для всех. возможная длина ввода. Таким образом, отдельная вычислительная проблема связана с конкретным семейством логических схем, каждая из которых является схемой, обрабатывающей входы n битов. На эти семейства часто накладывается условие однородности , требующее существования некоторой, возможно, ограниченной по ресурсам машины Тьюринга, которая на входе n $C_{1},C_{2},\dots$ $C_{n}$ , выдает описание отдельной схемы . Когда эта машина Тьюринга имеет полином времени работы от n , семейство схем называется P-однородным. Более строгие требования к DLOGTIME -однородности представляют особый интерес при изучении классов схем с малой глубиной, таких как AC ⁰ или TC ⁰ . Когда границы ресурсов не указаны, язык является рекурсивным (т. Е. Разрешимым на машине Тьюринга) тогда и только тогда, когда язык определяется однородным семейством логических схем. $C_{n}$

Равномерное полиномиальное время

Семейство булевых схем является однородным за полиномиальное время, если существует детерминированная машина Тьюринга M такая, что $\{C_{n}:n\in \mathbb {N} \}$

M работает за полиномиальное время
Для всех , М выводит описание на входе $n\in \mathbb {N}$ $C_{n}$ $1^{n}$

Униформа Logspace

Семейство булевых схем является однородным по лог-пространству, если существует детерминированная машина Тьюринга M такая, что $\{C_{n}:n\in \mathbb {N} \}$

M работает в логарифмическом пространстве
Для всех , М выводит описание на входе $n\in \mathbb {N}$ $C_{n}$ $1^{n}$

История

Сложность схем восходит к Шеннону в 1949 г. ^[2], который доказал, что почти все булевы функции от n переменных требуют схемы размера Θ (2 ⁿ / n ). Несмотря на этот факт, теоретики сложности смогли доказать только суперполиномиальные нижние границы схемы для функций, явно построенных для того, чтобы их было сложно вычислить.

Чаще всего суперполиномиальные нижние оценки доказываются при определенных ограничениях на семейство используемых схем. Первой функцией, для которой были показаны нижние границы суперполиномиальной схемы, была функция четности , которая вычисляет сумму своих входных битов по модулю 2. Тот факт, что четность не содержится в AC 0, был впервые независимо установлен Аджтаем в 1983 году ^[3]^{[4 ]} и Ферстом, Саксом и Сипсером в 1984 году. ^[5] Более поздние усовершенствования Хастада в 1987 году ^[6] установили, что любое семейство схем постоянной глубины, вычисляющих функцию четности, требует экспоненциального размера. Расширение результата Разборова ^[7] Смоленского в 1987 г. ^[8]Доказано, что это верно, даже если схема дополнена элементами, вычисляющими сумму ее входных битов по модулю некоторого нечетного простого числа p .

Задача k -клика состоит в том, чтобы решить, имеет ли данный граф на n вершинах клику размера k . Для любого конкретного выбора констант n и k граф может быть закодирован в двоичном формате с использованием битов, которые указывают для каждого возможного края, присутствует ли он. Тогда проблема k -клика формализуется как функция , которая выводит 1 тогда и только тогда, когда граф, закодированный строкой, содержит клику размера k ${n \choose 2}$ $f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}$ $f_{k}$ . Это семейство функций монотонно и может быть вычислено семейством схем, но было показано, что оно не может быть вычислено семейством монотонных схем полиномиального размера (то есть схем с логическими элементами И и ИЛИ, но без отрицания). Первоначальный результат Разборова 1985 года ^[7] был позже улучшен до экспоненциальной нижней границы Алон и Боппана в 1987 году. ^[9] В 2008 году Россман ^[10] показал, что схемы постоянной глубины с И, ИЛИ и НЕ воротам требуется размер для решения задачи k -клика даже в среднем случае . Кроме того, существует схема большого размера, которая производит вычисления . $\Omega (n^{k/4})$ $n^{k/4+O(1)}$ $f_{k}$

В 1999 году Раз и Маккензи позже показали, что монотонная иерархия NC бесконечна. ^[11]

Проблема целочисленного деления лежит в равномерном TC 0 . ^[12]

Нижние границы схемы

Нижние границы схемы обычно трудны. Известные результаты включают

Четность отсутствует в неоднородном AC 0 , что было доказано Айтаи в 1983 году ^[3]^[4], а также Ферстом, Саксом и Сипсером в 1984 году. ^[5]
Равномерный TC 0 строго содержится в PP , что доказал Аллендер. ^[13]
Классы SП 2, PP ^{[nb 1]} и MA / 1 ^[14] (MA с одним битом совета) не входят в SIZE ( n ^k ) для любой константы k.
Хотя есть подозрения, что неоднородный класс ACC 0 не содержит функции большинства, Уильямс доказал это только в 2010 году . ^[15] ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$

Неизвестно, имеет ли NEXPTIME неоднородные цепи TC ⁰ .

Доказательства нижних оценок схемы сильно связаны с дерандомизацией . Доказательство, которое означало бы, что любой или этот перманент не может быть вычислен с помощью неоднородных арифметических схем (полиномов) полиномиального размера и полиномиальной степени. ^[16] ${\mathsf {P}}={\mathsf {BPP}}$ ${\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}$

В 1997 году Разборов и Рудич показали, что многие известные нижние границы схемы для явных булевых функций подразумевают существование так называемых естественных свойств, полезных для соответствующего класса схем. ^[17] С другой стороны, естественные свойства, полезные против P / poly, нарушили бы сильные генераторы псевдослучайных ситуаций. Это часто интерпретируется как барьер "естественного доказательства" для доказательства строгих нижних оценок схемы. В 2016 году Кармозино, Импальяццо, Кабанец и Колоколова доказали, что природные свойства также могут быть использованы для построения эффективных алгоритмов обучения. ^[18]

Классы сложности

Многие классы сложности схемы определены в терминах иерархии классов. Для каждого неотрицательного целого числа i существует класс NC i , состоящий из схем глубины полиномиального размера , использующих ограниченные логические элементы И, ИЛИ и НЕ. Объединение NC всех этих классов является предметом обсуждения. Рассматривая неограниченные входные элементы, можно построить классы AC i и AC (равные NC). Многие другие классы сложности схем с такими же ограничениями по размеру и глубине могут быть построены путем разрешения различных наборов вентилей. $O(\log ^{i}(n))$

Отношение к временной сложности

Если определенный язык ,, принадлежит к классу временной сложности для некоторой функции , то имеет сложность схемы . ^[1] $A$ ${\text{TIME}}(t(n))$ $t:\mathbb {N} \to \mathbb {N}$ $A$ ${\mathcal {O}}(t^{2}(n))$

Смотрите также

Минимизация схемы

Примечания

^ См. Доказательство .

использованная литература

^ a b Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). Бостон, США: Издательская компания PWS. п. 324.
^ Шеннон, Клод Элвуд (1949). «Синтез двухполюсных коммутационных схем». Технический журнал Bell System . 28 (1): 59–98. DOI : 10.1002 / j.1538-7305.1949.tb03624.x .
^ а б Айтай, Миклош (1983). « -формулы на конечных структурах» . Летопись чистой и прикладной логики . 24 : 1–24. DOI : 10.1016 / 0168-0072 (83) 90038-6 . Σ 1 1 {\displaystyle \Sigma _{1}^{1}}
^ а б Айтай, Миклош ; Комлос, Янош; Семереди, Эндре (1983). Сеть сортировки 0 (n log n) . STOC '83 Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений . С. 1–9. ISBN 978-0-89791-099-6.
^ a b Ферст, Меррик Л .; Сакс, Джеймс Бенджамин ; Сипсер, Майкл Фредрик (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. DOI : 10.1007 / BF01744431 . Руководство по ремонту 0738749 .
^ Håstad, Йохан Torkel (1987). Вычислительные ограничения схем малой глубины (PDF) (кандидатская диссертация). Массачусетский Институт Технологий.
^ a b Разборов, Александр Александрович (1985). «Нижние оценки монотонной сложности некоторых булевых функций». Советская математика - Доклады . 31 : 354–357. ISSN 0197-6788 .
↑ Смоленский, Роман (1987). «Алгебраические методы в теории нижних оценок сложности булевых схем». Материалы 19-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 77–82. DOI : 10.1145 / 28395.28404 .
^ Алон, Нога ; Боппана, Рави Б. (1987). «Монотонная схемная сложность булевых функций». Combinatorica . 7 (1): 1-22. CiteSeerX 10.1.1.300.9623 . DOI : 10.1007 / bf02579196 .
^ Россман, Бенджамин Э. (2008). «О постоянной глубине сложности k-клики». STOC 2008: Материалы 40-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 721–730. DOI : 10.1145 / 1374376.1374480 .
^ Раз, Ран ; Маккензи, Пьер (1999). «Выделение монотонной иерархии НК». Combinatorica . 19 (3): 403–435. DOI : 10.1007 / s004930050062 .
^ Гессен, Уильям (2001). «Дивизия в униформе ТК ⁰ ». Материалы 28-го Международного коллоквиума по автоматам, языкам и программированию . Springer Verlag . С. 104–114.
^ Аллендер, Эрик Уоррен , изд. (1997). «Сложность схемы перед рассветом нового тысячелетия» (PDF) . [1] (NB. Обзор этой области в 1997 г., сделанный Эриком Аллендером.)
^ Santhanam, Рахул (2007). "Схема нижних оценок классов Мерлина-Артура" . STOC 2007: Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . С. 275–283. CiteSeerX 10.1.1.92.4422 . DOI : 10.1145 / 1250790.1250832 .
^ Уильямс, Ричард Райан (2011). "Неоднородные нижние границы цепи ACC" (PDF) . CCC 2011: Материалы 26-й ежегодной конференции IEEE по вычислительной сложности . С. 115–125. DOI : 10,1109 / CCC.2011.36 .
^ Кабанец, Валентин ; Impagliazzo, Рассел Грэм (2004). «Дерандомизация тестов полиномиальной идентичности означает доказательство нижних границ схемы». Вычислительная сложность . 13 (1): 1–46. DOI : 10.1007 / s00037-004-0182-6 .
^ Разборов, Александр Александрович ; Рудич, Стивен (1997). «Естественные доказательства». Журнал компьютерных и системных наук . 55 . С. 24–35.
^ Кармозино, Марко; Impagliazzo, Рассел Грэм ; Кабанец, Валентин ; Колоколова, Антонина (2016). «Изучение алгоритмов на основе естественных доказательств». Конференция по вычислительной сложности .

дальнейшее чтение

Фоллмер, Хериберт (1999). Введение в сложность схем: единый подход . Тексты по теоретической информатике. Серия EATCS. Springer Verlag . ISBN 978-3-540-64310-4.
Вегенер, Инго (1987) [ноябрь 1986]. Сложность булевых функций . Ряды Вили – Тойбнера в компьютерных науках. Франкфурт-на-Майне / Билефельд, Германия: John Wiley & Sons Ltd. и BG Teubner Verlag , Штутгарт. ISBN 3-519-02107-2. LCCN 87-10388 .(xii + 457 страниц) (NB. В то время влиятельный учебник по этому предмету, широко известный как «Синяя книга». Также доступен для загрузки (PDF) на Электронном коллоквиуме по вычислительной сложности .)
Цвик, Ури . «Конспект лекций по курсу Ури Цвика по сложности схем» .

[NB1-14] См. Доказательство .

[Sipser_1997-1] Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). Бостон, США: Издательская компания PWS. п. 324.

[Shannon_1949-2] Шеннон, Клод Элвуд (1949). «Синтез двухполюсных коммутационных схем». Технический журнал Bell System . 28 (1): 59–98. DOI : 10.1002 / j.1538-7305.1949.tb03624.x .

[Ajtai_1983-3] а б Айтай, Миклош (1983). « -формулы на конечных структурах» . Летопись чистой и прикладной логики . 24 : 1–24. DOI : 10.1016 / 0168-0072 (83) 90038-6 . Σ 1 1 {\displaystyle \Sigma _{1}^{1}}

[Ajtai-Komlós-Szemerédi_1983-4] а б Айтай, Миклош ; Комлос, Янош; Семереди, Эндре (1983). Сеть сортировки 0 (n log n) . STOC '83 Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений . С. 1–9. ISBN 978-0-89791-099-6.

[Furst-Saxe-Sipser_1984-5] Ферст, Меррик Л .; Сакс, Джеймс Бенджамин ; Сипсер, Майкл Фредрик (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. DOI : 10.1007 / BF01744431 . Руководство по ремонту 0738749 .

[Håstad_1987-6] Håstad, Йохан Torkel (1987). Вычислительные ограничения схем малой глубины (PDF) (кандидатская диссертация). Массачусетский Институт Технологий.

[Razborov_1985-7] Разборов, Александр Александрович (1985). «Нижние оценки монотонной сложности некоторых булевых функций». Советская математика - Доклады . 31 : 354–357. ISSN 0197-6788 .

[Smolensky_1987-8] Смоленский, Роман (1987). «Алгебраические методы в теории нижних оценок сложности булевых схем». Материалы 19-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 77–82. DOI : 10.1145 / 28395.28404 .

[Alon-Boppana_1987-9] Алон, Нога ; Боппана, Рави Б. (1987). «Монотонная схемная сложность булевых функций». Combinatorica . 7 (1): 1-22. CiteSeerX 10.1.1.300.9623 . DOI : 10.1007 / bf02579196 .

[Rossman_2008-10] Россман, Бенджамин Э. (2008). «О постоянной глубине сложности k-клики». STOC 2008: Материалы 40-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 721–730. DOI : 10.1145 / 1374376.1374480 .

[Raz-McKenzie_1999-11] Раз, Ран ; Маккензи, Пьер (1999). «Выделение монотонной иерархии НК». Combinatorica . 19 (3): 403–435. DOI : 10.1007 / s004930050062 .

[Hesse_2001-12] Гессен, Уильям (2001). «Дивизия в униформе ТК ⁰ ». Материалы 28-го Международного коллоквиума по автоматам, языкам и программированию . Springer Verlag . С. 104–114.

[Allender_1997-13] Аллендер, Эрик Уоррен , изд. (1997). «Сложность схемы перед рассветом нового тысячелетия» (PDF) . [1] (NB. Обзор этой области в 1997 г., сделанный Эриком Аллендером.)

[Santhanam_2007-15] Santhanam, Рахул (2007). "Схема нижних оценок классов Мерлина-Артура" . STOC 2007: Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . С. 275–283. CiteSeerX 10.1.1.92.4422 . DOI : 10.1145 / 1250790.1250832 .

[Williams_2011-16] Уильямс, Ричард Райан (2011). "Неоднородные нижние границы цепи ACC" (PDF) . CCC 2011: Материалы 26-й ежегодной конференции IEEE по вычислительной сложности . С. 115–125. DOI : 10,1109 / CCC.2011.36 .

[Kabanets-Impagliazzo_2004-17] Кабанец, Валентин ; Impagliazzo, Рассел Грэм (2004). «Дерандомизация тестов полиномиальной идентичности означает доказательство нижних границ схемы». Вычислительная сложность . 13 (1): 1–46. DOI : 10.1007 / s00037-004-0182-6 .

[Razborov-Rudich_1997-18] Разборов, Александр Александрович ; Рудич, Стивен (1997). «Естественные доказательства». Журнал компьютерных и системных наук . 55 . С. 24–35.

[Carmosino-Impagliazzo-Kabanets-Kolokolova_2016-19] Кармозино, Марко; Impagliazzo, Рассел Грэм ; Кабанец, Валентин ; Колоколова, Антонина (2016). «Изучение алгоритмов на основе естественных доказательств». Конференция по вычислительной сложности .