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

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

Определение Функция $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))\,$.

Ссылки

• Курс Н. П. Варновского Понятия теории сложности вычислений