В теоретической информатике сложность схемы — это раздел теории сложности вычислений , в котором булевы функции классифицируются в соответствии с размером или глубиной булевых схем , которые их вычисляют. Связанное понятие — сложность схемы рекурсивного языка , которая определяется однородным семейством схем (см. ниже).
Доказательство нижних границ размера булевых схем, вычисляющих явные булевы функции, является популярным подходом к разделению классов сложности. Например, известный класс схем P/poly состоит из булевых функций, вычисляемых схемой полиномиального размера. Доказательство этого разделило бы P и NP (см. ниже).
Классы сложности, определенные в терминах булевых схем, включают AC 0 , AC , TC 0 , NC 1 , NC и P/poly .
Булева схема с входными битами — это направленный ациклический граф , в котором каждый узел (обычно называемый в этом контексте вентилями ) является либо входным узлом входящей степени 0, помеченным одним из входных битов, вентилем И , вентилем ИЛИ или вентилем НЕ . Один из этих вентилей обозначается как выходной вентилем. Такая схема естественным образом вычисляет функцию своих входов. Размер схемы — это количество вентилей, которые она содержит, а ее глубина — это максимальная длина пути от входного вентиля до выходного вентиля.
Существует два основных понятия сложности схемы [1] Сложность размера схемы булевой функции — это минимальный размер любого вычисления схемы . Сложность глубины схемы булевой функции — это минимальная глубина любого вычисления схемы .
Эти понятия обобщаются, когда мы рассматриваем сложность схемы любого языка, который содержит строки с разной длиной бит, особенно бесконечные формальные языки . Булевы схемы, однако, допускают только фиксированное количество входных бит. Таким образом, ни одна булева схема не способна определить такой язык. Чтобы учесть эту возможность, мы рассматриваем семейства схем , где каждая принимает входные данные размера . Каждое семейство схем будет естественным образом генерировать язык с помощью выходных данных схемы , когда строка длины является членом семейства, и в противном случае. Мы говорим, что семейство схем имеет минимальный размер, если нет другого семейства, которое принимает решения о входных данных любого размера, , со схемой меньшего размера, чем (соответственно для семейств с минимальной глубиной ). Таким образом, сложность схемы имеет смысл даже для нерекурсивных языков . Понятие однородного семейства позволяет связать варианты сложности схемы с мерами сложности рекурсивных языков на основе алгоритмов. Однако неоднородный вариант полезен для нахождения нижних границ того, насколько сложным должно быть любое семейство схем, чтобы определить заданные языки.
Следовательно, сложность размера схемы формального языка определяется как функция , которая связывает длину входных данных в битах, , со сложностью размера схемы минимальной схемы , которая решает, находятся ли входные данные этой длины в . Сложность глубины схемы определяется аналогично.
Булевы схемы являются одним из основных примеров так называемых неоднородных моделей вычислений в том смысле, что входные данные разной длины обрабатываются разными схемами, в отличие от однородных моделей, таких как машины Тьюринга , где одно и то же вычислительное устройство используется для всех возможных длин входных данных. Таким образом, отдельная вычислительная задача связана с определенным семейством булевых схем , где каждая представляет собой схему, обрабатывающую входные данные из n бит. Условие однородности часто накладывается на эти семейства, требуя существования некоторой, возможно, ограниченной по ресурсам машины Тьюринга, которая на входе n производит описание отдельной схемы . Когда эта машина Тьюринга имеет полиномиальное по n время выполнения , семейство схем называется P-однородным. Более строгое требование DLOGTIME -однородности представляет особый интерес при изучении классов схем малой глубины, таких как AC 0 или TC 0 . Если ограничения ресурсов не указаны, язык является рекурсивным (т.е. разрешимым машиной Тьюринга) тогда и только тогда, когда язык определяется однородным семейством булевых схем.
Семейство булевых схем является однородным за полиномиальное время , если существует детерминированная машина Тьюринга M , такая, что
Семейство булевых схем является однородным в логарифмическом пространстве , если существует детерминированная машина Тьюринга M , такая, что
Сложность схем восходит к Шеннону в 1949 году [2], который доказал, что почти все булевы функции от n переменных требуют схем размера Θ(2 n / 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 -клики даже в среднем случае . Более того, существует схема размера , которая вычисляет .
В 1999 году Раз и Маккензи показали, что монотонная иерархия NC бесконечна. [11]
Задача о целочисленном делении лежит в однородном TC 0 . [12]
Нижние границы схемы обычно сложны. Известные результаты включают
Открыто, имеет ли NEXPTIME неоднородные цепи TC 0 .
Доказательства нижних границ схем тесно связаны с дерандомизацией . Доказательство, которое подразумевает, что либо , либо этот перманент не может быть вычислен неоднородными арифметическими схемами (многочленами) полиномиального размера и полиномиальной степени. [16]
В 1997 году Разборов и Рудич показали, что многие известные нижние границы схем для явных булевых функций подразумевают существование так называемых естественных свойств, полезных против соответствующего класса схем. [17] С другой стороны, естественные свойства, полезные против P/poly, сломали бы сильные псевдослучайные генераторы. Это часто интерпретируется как барьер «естественных доказательств» для доказательства сильных нижних границ схем. В 2016 году Кармосино, Импальяццо, Кабанец и Колоколова доказали, что естественные свойства также могут быть использованы для построения эффективных алгоритмов обучения. [18]
Многие классы сложности схем определяются в терминах иерархий классов. Для каждого неотрицательного целого числа i существует класс NC i , состоящий из схем полиномиального размера глубины , использующих ограниченные вентили AND, OR и NOT с вентилями ...
Если определенный язык, , принадлежит к классу временной сложности для некоторой функции , то имеет сложность схемы . Если машина Тьюринга, которая принимает язык, забывчива (что означает, что она читает и записывает одни и те же ячейки памяти независимо от ввода), то имеет сложность схемы . [19]
Монотонная булева схема — это схема, которая имеет только вентили И и ИЛИ, но не имеет вентилей НЕ. Монотонная схема может вычислять только монотонную булеву функцию, которая является функцией, где для каждого , , где означает, что для всех .