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

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

{\ Displaystyle \ клин}

{\ displaystyle \ vee}

{\ displaystyle \ neg}

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

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

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

Размер и глубина [ править ]

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

Существует два основных понятия сложности схемы (они описаны в Sipser (1997) ^[1]^{: 324} ). Схема размера сложность булевой функции является минимальным размером любой схемы вычислений . Схема глубина сложность булевой функции является минимальной глубиной любой схемы вычислений . ${\ 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}}$

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

Единообразие [ править ]

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

Полиномиальное время [ править ]

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

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

Униформа Logspace [ править ]

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

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

История [ править ]

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

Чаще всего суперполиномиальные нижние оценки доказываются при определенных ограничениях на семейство используемых схем. Первой функцией, для которой были показаны нижние границы суперполиномиальной схемы, была функция четности , которая вычисляет сумму своих входных битов по модулю 2. Тот факт, что четность не содержится в AC 0, был впервые независимо установлен Ajtai (1983) ^[2] и Авторы Furst, Saxe и Sipser (1984). ^[3] Более поздние улучшения Хастада.(1987) фактически установили, что любое семейство схем постоянной глубины, вычисляющих функцию четности, требует экспоненциального размера. Расширяя результат Разборова, Смоленский (1987) доказал, что это верно, даже если схема дополнена элементами, вычисляющими сумму ее входных битов по модулю некоторого нечетного простого числа p .

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

Позже Раз и Маккензи показали, что монотонная иерархия NC бесконечна (1999).

Проблема целочисленного деления лежит в однородном TC 0 (Hesse 2001).

Нижние границы схемы [ править ]

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

Четность отсутствует в неоднородном AC 0 , что доказано Ajtai (1983) и Furst, Saxe и Sipser.
Равномерный TC 0 строго содержится в PP , что доказал Аллендер.
Классы SP 2, PP ^[4] и MA / 1 ^[5] (MA с одним битом совета) не входят в SIZE (n ^k ) для любой константы k.
Хотя есть подозрения, что неоднородный класс ACC 0 не содержит функции большинства, Уильямс доказал это только в 2010 году . ^[6] ${\ Displaystyle {\ mathsf {NEXP}} \ not \ substeq {\ mathsf {ACC}} ^ {0}}$

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

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

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

Классы сложности [ править ]

Многие классы сложности схемы определены в терминах иерархии классов. Для каждого неотрицательного целого числа 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))$

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

^ а б Сипсер, М. (1997). «Введение в теорию вычислений». Бостон: паб PWS. Co.
^ Айтай, Миклош; Комлос, Янош; Семереди, Эндре (1983). Сеть сортировки 0 (n log n) . STOC '83 Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений . С. 1–9. ISBN 978-0-89791-099-6.
^ Ферст, Меррик; Сакс, Джеймс Б .; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. DOI : 10.1007 / BF01744431 . Руководство по ремонту 0738749 .
^ См. Доказательство
^ 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). «Изучение алгоритмов на основе естественных доказательств». Конференция по вычислительной сложности .

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

Айтай, Миклош (1983). « -формулы на конечных структурах». Летопись чистой и прикладной логики . 24 : 1–24. DOI : 10.1016 / 0168-0072 (83) 90038-6 . $\Sigma _{1}^{1}$
Алон, Нога; Боппана, Рави Б. (1987). «Монотонная схемная сложность булевых функций». Combinatorica . 7 (1): 1-22. CiteSeerX 10.1.1.300.9623 . DOI : 10.1007 / bf02579196 .
Furst, Merrick L .; Saxe, Джеймс Б.; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. DOI : 10.1007 / bf01744431 .
Хостад, Йохан (1987), Вычислительные ограничения схем малой глубины (PDF) , Ph.D. докторская диссертация, Массачусетский технологический институт.
Гессен, Уильям (2001). «Дивизия в униформе ТК ⁰ ». Proc. 28-й Международный коллоквиум по автоматам, языкам и программированию . Springer. С. 104–114.
Раз, Ран; Маккензи, Пьер (1999). «Выделение монотонной иерархии НК». Combinatorica . 19 (3): 403–435. DOI : 10.1007 / s004930050062 .
Разборов, Александр А. (1985). «Нижние оценки монотонной сложности некоторых булевых функций». Математика СССР, Докл . 31 : 354–357.
Россман, Бенджамин (2008). «О постоянной глубине сложности k-клики». STOC 2008: Материалы 40-го ежегодного симпозиума ACM по теории вычислений . ACM. С. 721–730. DOI : 10.1145 / 1374376.1374480 .
Шеннон, Клод Э. (1949). «Синтез двухполюсных коммутационных схем». Технический журнал Bell System . 28 (1): 59–98. DOI : 10.1002 / j.1538-7305.1949.tb03624.x .
Смоленский, Роман (1987). «Алгебраические методы в теории нижних оценок сложности булевых схем». Proc. 19-й ежегодный симпозиум ACM по теории вычислений . ACM. С. 77–82. DOI : 10.1145 / 28395.28404 .
Фоллмер, Хериберт (1999). Введение в сложность схем: единый подход . Springer Verlag . ISBN 978-3-540-64310-4.
Вегенер, Инго (1987). Сложность булевых функций . John Wiley and Sons Ltd и BG Teubner, Штутгарт. ISBN 978-3-519-02107-0.В то время влиятельный учебник по этому предмету, широко известный как «Синяя книга». Также доступен для загрузки (PDF) на Электронном коллоквиуме по вычислительной сложности .
Конспект лекций по курсу Ури Цвика по сложности схем
Сложность схемы перед рассветом нового тысячелетия , обзор этой области Эрик Аллендер в 1997 году слайды .

[Sipser-1] а б Сипсер, М. (1997). «Введение в теорию вычислений». Бостон: паб PWS. Co.

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

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

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

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

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

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

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

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