Условия управляемости 3SAT-Удовлетворенность

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

Предположим, например, класс задач 3SAT, что из возможных назначений удовлетворяет булевой формуле; мы можем эффективно найти удовлетворяющее задание? Для чего возникает проблема в P? $\epsilon(n) 2^n$ $2^n$ $\epsilon$

Редактировать заметку: Заменить на чтобы убрать путаницу. $\epsilon$ $\epsilon(n)$

cc.complexity-theory ds.algorithms sat np Рафи Виттен
источник

Простое наблюдение: если не более чем обратно полиномиально мало, то выборка равномерно раз даст решение за ожидаемое полиномиальное время. Так что если находится между 1 и 1 / poly (n), эта проблема проста (это в ZPP).

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

ϵ

$\epsilon$

Робин Котари

аналогично, если 1 / eps является квазиполиномиальным, то у вас есть алгоритм рандомизированного квазиполичного времени, что само по себе было бы удивительно

Суреш Венкат

Да. Если является константой (или ), и вам обещано, что по крайней мере из всех возможных назначений удовлетворяют входным 3CNF, то вы можете найти такое назначение в детерминированном полиномиальном времени. $0< \epsilon <1$ $1/\textit{polylog}(n)$ $\epsilon 2^n$

Алгоритмы не сложные:

Утверждение: Под обещание указано, должно существовать множество размер постоянной переменных, ударяется все пункты в 3CNF, в том смысле , что каждый 3-пункт должен содержать переменную из . $S$ $S$

Доказательство утверждения (эскиз): в противном случае должно существовать достаточно большое семейство 3-пунктов из 3CNF, в котором каждая переменная встречается только один раз. Но эта семья, когда достаточно большой, имеет уже меньше , чем доля удовлетворяющих назначений. QED $\epsilon$

Таким образом, вы можете работать по всем возможным (постоянное число) назначений на . При каждом фиксированном назначении 3CNF становится 2CNF, исходя из предположения, что поражает исходную 3CNF. Теперь вы можете использовать известный многочленный детерминистический алгоритм для нахождения удовлетворительного назначения для формул 2CNF. В целом, вы получаете верхнюю границу полиномиального времени. $S$ $S$ $S$

Алгоритм 2SAT, я думаю, уже в известной статье С. Кука 1971 года.

Алгоритм для 3CNF взят из: Л. Тревизана . Замечание о детерминированном приближенном подсчете для k-DNF в Proc. APPROX-RANDOM, Springer-Verlag, стр. 417-426, 2004

Исходная статья, показывающая результат для 3CNF: Э. Хирш, Быстрый детерминированный алгоритм для формул, которые имеют много удовлетворяющих заданий , Журнал IGPL, 6 (1): 59-71, 1998

Иддо Цамерет
источник

Спасибо за ответ. Я действительно интересовался непостоянным но изучение существования детерминированного алгоритма интересно. Я отредактировал вопрос, чтобы сделать его более понятным.

ϵ

$\epsilon$

Рафи Виттен

@Rafi, я думаю, что тот же алгоритм работает для непостоянных .

ϵ = 1 / p o l y l o g (n)

$\epsilon = 1/polylog(n)$

Иддо Цамерет

Как вы строите S?

Раду GRIGore

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

C_{1}

$C_1$

C_{2}

$C_2$

C_{1}

$C_1$

Иддо Цамерет

Условия управляемости 3SAT-Удовлетворенность

Ответы: