Схемная сложность

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Схемная сложность — сложность (число элементов) функциональной схемы, вычисляющей заданную функцию (семейство функций). Полиномиальная схемная сложность не зависит от выбора базиса функциональных элементов для построения схемы.

Определение Функция \(f\,\) вычислима семейством схем полиномиального размера, если существуют семейство схем \(\{ C_n\}\,\) и полином \(p\,\) такие, что для всякого \(n\,\) схема \(C_n\,\) вычисляет функцию \(f_n\,\) и при этом \(|C_n|\leq p(n)\,\).

Заметим, что поскольку схемная сложность нас интересует с точностью до полиномиальных множителей, это определение не зависит от выбора базиса.

Семейство схем полиномиального размера — более мощная модель вычислителя, чем полиномиальная машина Тьюринга. В частности, очевидно, что такие семейства схем существуют для некоторых очень сложно вычислимых (на машинах Тьюринга), и даже нерекурсивных, функций. Ответ на вопрос, для всех ли языков из класса P существуют семейства схем полиномиального размер, дает следующая теорема.

Теорема Если язык \(L\,\) распознается на детерминированной машине Тьюринга за время \(T(n)\,\), то для \(L\,\) существует семейство схем размера \(O(T^2(n))\,\).

Доказательство Пусть \(M\,\) — машина Тьюринга, распознающая язык \(L\,\) за время \(T(n)\,\), где \(n\,\) — длина входа. Из ограничения на время следует, что на любом входе длины \(n\,\) машина \(M\,\) использует не более \(T(n)\,\) ячеек памяти на ленте. Построим для данного \(n\,\) таблицу размера \(T(n)\times T(n)\,\), в которой \(i\,\)-ая строка описывает состояние вычисления в момент времени \(i\,\). Более точно, элемент таблицы с индексами \((i,j)\,\) содержит пару \((q,a)\,\), что означает, что в момент времени \(i\,\) машина \(M\,\) находится в состоянии \(q\,\) и обозревает \(j\,\)-ую ячейку, в которой записан символ \(a\,\). Подчеркнем, что \(q\,\) и \(a\,\) — переменные, которые принимают значения в множестве состояний \(Q\,\) и в алфавите \(A\,\) машины \(M\,\) соответственно. По определению машины Тьюринга, множества \(Q\,\) и \(A\,\) конечны. Поэтому существует такая константа \(k\,\) (не зависящая от длины входа \(n\,\)), что пару \((q,a)\,\) можно представить \(k\,\)-битовой строкой \(b_{i,j}\,\). Далее, из определения машины Тьюринга следует также, что элемент таблицы с индексами \((i,j)\,\) может зависеть только от трех других элементов, а именно, от \((i-1,j-1)\,\), \((i-1,j)\,\) и \((i-1,j+1)\,\). Таким образом, каждый бит строки \(b_{i,j}\,\) является булевой функцией \(3k\,\) битов строк \(b_{i-1,j-1}\,\), \(b_{i-1,j}\,\) и \(b_{i-1,j+1}\,\). Для каждого элемента \((i,j)\,\) можно построить схему из функциональных элементов, которая вычисляет его значение исходя из значений элементов \((i-1,j-1)\,\), \((i-1,j)\,\) и \((i-1,j+1)\,\). Очевидно, что эта элементарная схема имеет константную сложность.

Требуемая схема \(C_n\,\) строится путем очевидного объединения всех элементарных схем. Остается только определить выход схемы \(C_n\,\). Без ограничения общности можно считать, что машина \(M\,\) работает на каждом входе длины \(n\,\) в точности \(T(n)\,\) тактов и перед остановом записывает результат своей работы в первую ячейку ленты (1, если входное слово принимается, и 0, если оно отвергается). Поэтому выходом всей схемы \(C_n\,\) можно объявить выход элементарной схемы с индексами \((T(n),1)\,\), соответствующий первой ячейке ленты.

Ясно, что суммарная сложность всех элементарных схем имеет порядок \(O(T^2(n))\,\).

В доказательстве предполагалось, что машина \(M\,\) является одноленточной. Однако, из теории сложности известно, что произвольная многоленточная машина Тьюринга, работающая за время \(T(n)\,\), моделируется на одноленточной машине со сложностью \(O(T^2(n))\,\). Поэтому для любого языка, распознаваемого многоленточной машиной Тьюринга за время \(T(n)\,\), существует семейство схем размера \(O(T^4(n))\,\).

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