Для чего хороши схемы ограниченной длины?

14

Можно говорить о ширине дерева булевой схемы, определяя ее как ширину дерева «морализированного» графа на проводах (вершинах), полученного следующим образом: соединяйте провода a и б всякий раз, когда б является выходом затвора, имеющего вход a (или наоборот); подключайте провода a и б всякий раз, когда они используются в качестве входов к одному затвору. Редактировать: можно эквивалентно определить ширину линии схемы как графа, представляющего ее; если мы используем ассоциативность, чтобы переписать все вентили И и ИЛИ, чтобы иметь разветвление не более двух, ширина дерева в соответствии с любым определением будет одинаковой с коэффициентом 3 .

Существует, по крайней мере, одна проблема, которая, как известно, в общем случае неразрешима, но решаема в булевых схемах ограниченной длины дерева: учитывая вероятность того, что для каждого из входных проводов будет задано значение 0 или 1 (независимо от других), вычислите вероятность того, что определенный выходной вентиль равен 0 или 1. Это, как правило, # P-hard путем сокращения, например, # 2SAT, но это может быть решено в PTIME в цепях, длина дерева которых, как предполагается, меньше константы, с использованием алгоритма дерева соединений .

Мой вопрос заключается в том, чтобы узнать, существуют ли другие проблемы, помимо вероятностных вычислений, которые, как известно, трудно поддаются решению в общем случае, но поддаются решению для цепей с ограниченной шириной, или сложность которых можно описать как функцию от размера схемы, а также от ее ширины. Мой вопрос не относится к булеву случаю; Я также заинтересован в арифметических схемах над другими полуколец. Вы видите такие проблемы?

a3nm
источник
1
Для случая булевых схем с отрицанием (поэтому он не обобщается на арифметические схемы), теперь я понимаю, что проверка выполнимости или универсальности выполняется в PTIME. Без отрицания это всегда имеет место, но с отрицанием это обычно NP-жесткий (тривиально, путем сокращения от SAT), но это в PTIME (как особый случай вероятностного вывода) для случая цепей ограниченной длины. Но, тем не менее, меня это мало устраивает, так как это, по сути, та же проблема ...
a3nm

Ответы:

9

Теперь мы понимаем, что для любой фиксированной границы КN на ширине дерева мы можем преобразовать любую булеву схему с шириной дерева меньше, чем К в так называемую схему d-SDNNF за линейное время и с зависимостью от К являющейся однократно экспоненциальной.

Так называемые d-SDNNF - это схемы, удовлетворяющие условиям использования отрицания (только на листьях), детерминизма (входные данные для OR-элементов взаимно исключаются), разложимости (входные данные для AND-элементов зависят от непересекающихся множеств переменных). ) и структурированность (вентили AND разделяют переменные некоторым фиксированным образом по всей схеме, как описано в v-дереве). Этот класс был изучен в процессе компиляции знаний, и, как известно, он пользуется подсчитываемым SAT и посчитанным модельным подсчетом (повторная сбор вероятностных оценок и подсчет), но для этого класса были изучены другие проблемы, такие как перечисление , количественная оценка и т. Д.

Таким образом, один из способов использовать границы ширины дерева схемы - преобразовать ее в этот класс d-SDNNF, который имеет более явные свойства с точки зрения семантики схемы и для которого имеется несколько известных результатов о возможности выполнения различных задач.

a3nm
источник