Проводилось ли какое-либо исследование

Хорошо известной характеристикой экземпляров -SAT является отношение числа предложений m к числу переменных n , т. Е. Частное ρ = m / n . Для каждого k существует пороговое значение α st \ для ρ ≪ α , большинство случаев выполнимо, а для ρ ≫ α большинство случаев неудовлетворительно. Было проведено много исследований для задач, где ρ ≪ α , и для задач с достаточно малым ρ , $k$$m$$n$$\rho = m/n$$k$$\alpha$$\rho \ll \alpha$$\rho \gg \alpha$$\rho \ll \alpha$$\rho$$k$-SAT становится разрешимым за полиномиальное время. См., Например, обзорную статью Димитриса Ахлиопта из «Справочника по удовлетворенности» ( PDF ).

Мне интересно, была ли проделана какая-либо работа в другом направлении (где ), например, можем ли мы как-то трансформировать проблему из CNF в DNF в этом случае, чтобы решить ее быстро.$\rho \gg \alpha$

Итак, по существу, Что известно относительно SAT, где ?$\rho = m/n \gg \alpha$

Да, было. Моше Варди недавно выступил с докладом на семинаре BIRS по теоретическим основам прикладного SAT-решения :

• Моше Варди, Фазовые переходы и вычислительная сложность , 2014.

(Моше представляет график их эксперимента немного позже минуты 14:30 в своем выступлении, связанном выше.)

Обозначим через коэффициент клаузулы. По мере того, как значение ρ превышает пороговое значение, проблема становится проще для существующих решателей SAT, но не так легко, как это было до достижения порогового значения. По мере приближения к порогу снизу уровень сложности очень резко возрастает. После порога проблема становится легче по сравнению с порогом, но снижение сложности намного менее круто.$\rho$$\rho$

Обозначим через сложность задачи относительно n (в их эксперименте T ρ ( n ) - это среднее время работы GRASP на случайных 3SAT-экземплярах с отношением предложений ρ ). Моше предполагает, что T ρ ( n ) изменяется следующим образом:$T_\rho(n)$$n$$T_\rho(n)$$\rho$$T_\rho(n)$

• порог: T ρ ( n ) является полиномом от n ,$\rho \ll$$T_\rho(n)$$n$
• находится вблизи порога: T ρ ( n ) экспоненциально по n ,$\rho$$T_\rho(n)$$n$
• порог: T ρ ( n ) остается экспоненциальным по n, но показатель степени уменьшается сувеличением ρ .$\rho \gg$$T_\rho(n)$$n$$\rho$

$k\text-\mathsf{SAT}$

• Для таких формул показаны нижние оценки длины опровержений в разрешении и более сильные пропозициональные системы доказательств, начиная с статьи « Много сложных примеров для разрешения » Хватала и Семереди. Эти нижние границы разрешения означают более низкие границы времени выполнения SAT-решателей на основе DPLL и CDCL. Самые сильные нижние оценки относятся к исчислению полиномов благодаря Бен-Сассону и Импальяццо .
• Для таких формул существуют эффективные детерминированные алгоритмы для сертификации неудовлетворенности, то есть алгоритмы, которые либо выводят «UNSAT», либо «Don't Know», где ответ «UNSAT» должен быть правильным, и он должен выводить «UNSAT» в неудовлетворительные формулы с высокой вероятностью. Самые сильные результаты в этом направлении связаны с Фейге и Офеком .

Вот более старое, но актуальное исследование / ракурс ведущего эксперта.

• Скованность ножа лезвием Уолша 1998

$\kappa$

$\kappa$$\kappa$

$m/n \gg\alpha$