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

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

Пример булевой схемы. Узлы — это вентили И , узлы — это вентили ИЛИ , а узлы — это вентили НЕ ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle \neg }$

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

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

Классы сложности, определенные в терминах булевых схем, включают AC 0 , AC , TC 0 , NC 1 , 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}}$

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

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

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

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

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

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

Униформа Logspace

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

• M работает в логарифмическом рабочем пространстве (т.е. M является преобразователем логарифмического пространства )
• Для всех M выводит описание на входе ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle C_{n}}$ ${\displaystyle 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 . Это семейство функций является монотонным и может быть вычислено семейством схем, но было показано, что его нельзя вычислить семейством монотонных схем полиномиального размера (то есть схемами с вентилями И и ИЛИ, но без отрицания). Первоначальный результат Разборова 1985 года ^[7] был позже улучшен до нижней границы экспоненциального размера Алоном и Боппаной в 1987 году. ^[9] В 2008 году Россман ^[10] показал, что схемы постоянной глубины с вентилями И, ИЛИ и НЕ требуют размера для решения проблемы k -клики даже в среднем случае . Более того, существует схема размера , которая вычисляет . ${\displaystyle {n \choose 2}}$ ${\displaystyle f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}}$ ${\displaystyle f_{k}}$ ${\displaystyle \Omega (n^{k/4})}$ ${\displaystyle n^{k/4+O(1)}}$ ${\displaystyle 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 ⁰ не содержит функцию большинства, только в 2010 году Уильямс доказал это . ^[15] ${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}}$

Открытым остается вопрос о том, имеет ли NEXPTIME неоднородные цепи TC ^{0 .}

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

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

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

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

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

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

Монотонные схемы

Монотонная булева схема — это схема, которая имеет только вентили И и ИЛИ, но не имеет вентилей НЕ. Монотонная схема может вычислять только монотонную булеву функцию, которая является функцией, где для каждого , , где означает, что для всех . ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle x,y\in \{0,1\}^{n}}$ ${\displaystyle x\leq y\implies f(x)\leq f(y)}$ ${\displaystyle x\leq y}$ ${\displaystyle x_{i}\leq y_{i}}$ ${\displaystyle i\in \{1,\ldots ,n\}}$

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

• Минимизация цепи

Примечания

1. См . доказательство .

Ссылки

1. Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). Бостон, США: PWS Publishing Company. стр. 324.
2. Шеннон, Клод Элвуд (1949). «Синтез двухполюсных коммутационных схем». Bell System Technical Journal . 28 (1): 59–98. doi :10.1002/j.1538-7305.1949.tb03624.x.
3. Ajtai, Miklós (1983). " -формулы на конечных структурах". Annals of Pure and Applied Logic . 24 : 1–24. doi :10.1016/0168-0072(83)90038-6. ${\displaystyle \Sigma _{1}^{1}}$
4. Айтай, Миклош ; Комлос, Янош ; Семереди, Эндре (1983). « Сортировочная сеть». Материалы 15-го ежегодного симпозиума ACM по теории вычислений, 25–27 апреля 1983 г., Бостон, Массачусетс, США . Ассоциация вычислительной техники. стр. 1–9. дои : 10.1145/800061.808726. ${\displaystyle O(n\log n)}$
5. Furst, Merrick L.; Saxe, James Benjamin ; Sipser, Michael Fredric (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. doi :10.1007/BF01744431. MR  0738749. S2CID  6306235.
6. Хастад, Йохан Торкель (1987). Вычислительные ограничения схем малой глубины (PDF) (диссертация). Массачусетский технологический институт.
7. Разборов, Александр Александрович (1985). «Нижние оценки монотонной сложности некоторых булевых функций». Советская математика — Доклады . 31 : 354–357. ISSN  0197-6788.
8. Смоленский, Роман (1987). «Алгебраические методы в теории нижних оценок сложности булевых схем». Труды 19-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 77–82. doi : 10.1145/28395.28404 .
9. Алон, Нога ; Боппана, Рави Б. (1987). «Монотонная сложность схемы булевых функций». Комбинаторика . 7 (1): 1–22. CiteSeerX 10.1.1.300.9623 . дои : 10.1007/bf02579196. S2CID  17397273. 
10. Россман, Бенджамин Э. (2008). «О постоянной глубине сложности k-клики». STOC 2008: Труды 40-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 721–730. doi :10.1145/1374376.1374480.
11. Раз, Ран ; Маккензи, Пьер (1999). «Разделение монотонной иерархии NC». Combinatorica . 19 (3): 403–435. doi :10.1007/s004930050062.
12. Гессе, Уильям (2001). «Разделение в форме TC ⁰ ». Труды 28-го Международного коллоквиума по автоматам, языкам и программированию . Springer Verlag . С. 104–114.
13. Аллендер, Эрик (1996). «Сложность схем перед рассветом нового тысячелетия». В Чандру, Виджай; Винай, В. (ред.). Основы программных технологий и теоретической информатики, 16-я конференция, Хайдарабад, Индия, 18–20 декабря 1996 г., Труды . Заметки лекций по информатике. Том 1180. Springer. стр. 1–18. doi :10.1007/3-540-62034-6_33.
14. Сантханам, Рахул (2007). «Нижние границы цепей для классов Мерлина-Артура». STOC 2007: Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений . С. 275–283. CiteSeerX 10.1.1.92.4422 . doi :10.1145/1250790.1250832. 
15. Уильямс, Ричард Райан (2011). «Нижние границы неоднородных схем ACC» (PDF) . CCC 2011: Труды 26-й ежегодной конференции IEEE по вычислительной сложности . стр. 115–125. doi :10.1109/CCC.2011.36.
16. Кабанец, Валентин; Импальяццо, Рассел Грэм (2004). «Дерандомизация полиномиальных тестов идентичности означает доказательство нижних границ схемы». Computational Complexity . 13 (1): 1–46. doi :10.1007/s00037-004-0182-6. S2CID  12451799.
17. Разборов, Александр Александрович ; Рудич, Стивен (1997). «Естественные доказательства». Журнал компьютерных и системных наук . Т. 55. С. 24–35.
18. Кармосино, Марко; Импальяццо, Рассел Грэм ; Кабанец, Валентин; Колоколова, Антонина (2016). «Изучение алгоритмов на основе естественных доказательств». Computational Complexity Conference .
19. Пиппенджер, Николас ; Фишер, Майкл Дж. (1979). «Связи между мерами сложности». Журнал ACM . 26 (3): 361–381. doi : 10.1145/322123.322138 . S2CID  2432526.

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

• Vollmer, Heribert [на немецком языке] (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 страниц) (Примечание. В то время влиятельный учебник по предмету, широко известный как «Синяя книга». Также доступен для скачивания (PDF) на Electronic Colloquium on Computational Complexity .)
• Цвик, Ури . «Конспект лекций по курсу Ури Цвика по сложности схем».