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

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

модель вычислительной сложности

Пример логической схемы. Узлы

∧ {\ displaystyle \ wedge}

\ клин

- это логические элементы И, узлы

∨ {\ displaystyle \ vee}

\ vee

- это Логические элементы ИЛИ и узлы

¬ {\ displaystyle \ neg}

\ neg

являются вентилями НЕ

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

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

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

Содержание

1 Размер и глубина
2 Однородность
- 2.1 Полиномиальная временная однородность
- 2.2 Единообразный логпространство
3 История
4 Нижние границы схемы
5 Классы сложности
6 Отношение к временной сложности
7 Примечания
8 Ссылки

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

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

Существует два основных понятия сложности схемы (они описаны в Sipser (1997)). Сложность размера схемы логической функции $f {\ displaystyle f}$ $f$ - это минимальный размер любой схемы, вычисляющей $f {\ displaystyle f}$ $f$ . сложность схемы логической функции $f {\ displaystyle f}$ $f$ - это минимальная глубина любых схемных вычислений $f {\ displaystyle f}$ $f$ .

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

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

Однородность

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

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

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

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

Единообразное пространство журнала

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

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

История

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

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

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

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

Проблема целочисленного деления заключается в униформе TC (Hesse 2001).

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

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

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

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

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

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

Сложность классы

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

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

Скажем, что определенный язык, $A {\ displaystyle A}$ $A$ , принадлежит t he класс временной сложности $TIME (t (n)) {\ displaystyle {\ text {TIME}} (t (n))}$ ${\ text {TIME}} (t (n))$ для некоторой функции $t: N → N {\ displaystyle t: \ mathbb {N} \ to \ mathbb {N}}$ $t: {\ mathbb {N}} \ to {\ mathbb {N}}$ . Тогда $A {\ displaystyle A}$ $A$ имеет сложность схемы $O (t 2 (n)) {\ displaystyle {\ mathcal {O}} (t ^ {2} (n)) }$ ${\ ma thcal {O}} (t ^ {{2}} (n))$ .

Примечания

Ссылки

Айтай, Миклош (1983). « $Σ 1 1 {\ displaystyle \ Sigma _ {1} ^ {1}}$ $\ Sigma _ {1} ^ {1}$ -формулы конечных структур». Анналы чистой и прикладной логики. 24 : 1–24. doi : 10.1016 / 0168-0072 (83) 90038-6.
Алон, Нога; Боппана, Рави Б. (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.
Raz, Ran; Маккензи, Пьер (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). Введение в сложность схем: единый подход. Спрингер Верлаг. ISBN 978-3-540-64310-4.
Вегенер, Инго (1987). Сложность булевых функций. John Wiley and Sons Ltd и Б. Г. Тойбнер, Штутгарт. ISBN 978-3-519-02107-0.В то время влиятельный учебник по предмету, широко известный как «Синяя книга». Также доступны для загрузки (PDF) на Электронном коллоквиуме по вычислительной сложности.
Конспекты лекций по курсу Ури Цвика по сложности схем
Сложность схем до начала нового тысячелетия, обзор месторождения Эрик Аллендер в 1997 г. slides.