Какова корреляция между шириной дерева и твердостью экземпляра для случайного 3-SAT?

11

В этой недавней статье FOCS2013 « Сильные черные ходы к SAT ограниченной длины дерева», составленной Gaspers и Szeider, говорится о связи между шириной дерева графика предложения SAT и твердостью экземпляра.

Для случайных 3-SAT, то есть 3-SAT экземпляров, выбранных случайным образом, какова корреляция между шириной дерева графика предложений и твердостью экземпляра?

«Твердость экземпляра» можно принять как «сложность для типичного решателя SAT», то есть время работы.

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

Возможно, естественный тесно связанный с этим вопрос заключается в том, как древовидная графа раздела соотносится с фазовым переходом 3-SAT.

graph-algorithms sat treewidth random-k-sat hard-instances ВЗН
источник

10

Не совсем ответ, но самые близкие ссылки, о которых я знаю. Есть результаты, доступные для ширины ветви. Кроме того, существует по крайней мере одно эмпирическое исследование ширины промышленных экземпляров.

Обнаружение древовидной ширины , H. Bodlaender, 2005. Дает алгоритмы для вычисления границ древовидной ширины.
Treewidth в Industrial SAT Benchmarks , R. Mateescu, 2011. Использует варианты вышеуказанных алгоритмов для оценки ширины трассы SAT2009.
Алгоритмы и результаты сложности для #SAT и байесовского вывода , F. Bacchus S. Dalmao, T. Pitassi, 2003. Относительная ширина ветки к сложности #SAT, 2003.
Удовлетворенность, тавтология по широте и ширине ветвей , Алехнович, Разборов, 2002.

Виджай Д
источник

7

В общем случае не следует ожидать, что случайные экземпляры SAT будут иметь ограниченную ширину дерева, даже если они просты. Вот пример:

$n$ $3$ $\theta(n)$ $3$

$d$ $k$ $4 \cdot \frac{1}{2^k} \cdot dk \leq 1$ $d \leq \frac{2^k}{4k}$

$t$ $t$ $n/2$

Даниелло
источник

спасибо за идеи. ofc не ожидал, что случайные экземпляры будут иметь ограниченную длину дерева; противоположность предположительно доказуема без особых затруднений. но это числовой параметр, который можно сравнивать / коррелировать с твердостью аналогично многим другим параметрам, изученным в эмпирических исследованиях точки перехода SAT, и некоторая взаимосвязь или корреляция, по-видимому, ожидаются на основе существующих исследований.

августа

@vzn Суть в том, что в наиболее распространенных случайных моделях ширина дерева проходит через крышу, прежде чем экземпляры становятся вычислительно сложными. С другой стороны, экземпляры "реальной жизни", вероятно, имеют гораздо меньшую ширину дерева, чем случайные, и я ожидаю, что SAT-решатели воспользуются (некоторыми) преимуществами этого.

Даниелло

Какова корреляция между шириной дерева и твердостью экземпляра для случайного 3-SAT?

Ответы: