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

Пример логической схемы. $\wedge$ узлы — это вентили И , $\vee$ узлы являются вентилями ИЛИ , а $\neg$ узлы НЕ являются воротами

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

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

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

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

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

Существует два основных понятия сложности схемы. по размеру схемы Сложность булевой функции $f$ минимальный размер любого схемного вычисления $f$. булевой Сложность схемы функции $f$ - минимальная глубина любых схемных вычислений $f$.

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

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

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

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

Полиномиальное время

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

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

Логпространственная униформа

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

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

История

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

Суперполиномиальные нижние оценки были доказаны при определенных ограничениях на семейство используемых схем. Первой функцией, для которой были показаны нижние границы суперполиномиальной схемы, была функция четности , которая вычисляет сумму своих входных битов по модулю 2. Тот факт, что четность не содержится в AC ⁰ была впервые основана Аджтаем независимо в 1983 году. и Ферстом, Саксом и Сипсером в 1984 году. Более поздние улучшения Хостада в 1987 году. установил, что любое семейство схем постоянной глубины, вычисляющее функцию четности, требует экспоненциального размера. Продолжая результат Разборова, Смоленский в 1987 году. доказал, что это верно, даже если схема дополнена вентилями, вычисляющими сумму ее входных битов по модулю некоторого нечетного простого числа p .

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

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

Проблема целочисленного деления заключается в однородном TC ⁰ .

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

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

• Четность не в неоднородном переменном токе. ⁰ , доказано Аджтаем в 1983 г. а также Ферстом, Саксом и Сипсером в 1984 году.
• Униформа ТК ⁰ строго содержится в PP , доказанном Аллендером.
• Классы С ^П
  ₂ , ПП и МА /1 (МА с одним советом) не в РАЗМЕРЕ ( n ^к ) для любой константы k.
• Хотя есть подозрение, что неоднородный класс АСС ⁰ не содержит функции большинства, только в 2010 году Уильямс доказал, что ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$.

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

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

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

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

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

Связь со временной сложностью

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

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

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

См. также

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

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

• Фоллмер, Гериберт [на немецком языке] (1999). Введение в сложность схем: единый подход . Тексты по теоретической информатике. Серия EATCS. Спрингер Верлаг . 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) на Электронном коллоквиуме по вычислительной сложности .)
• Цвик, Ури . «Конспекты лекций по курсу Ури Цвика по сложности схем» .