Найти

9

Пусть будет языком всех -CNF-формул таким образом, чтобы по крайней мере из предложений можно было выполнить. $L_\epsilon$ $2$ $\varphi$ $(\frac{1}{2}+\epsilon)$ $\varphi$

Мне нужно доказать, что существует st is -hard для любого . $\epsilon'$ $L_\epsilon$ $\mathsf{NP}$ $\epsilon<\epsilon'$

Мы знаем, что может быть приближен к проценту пунктов из сокращения . Как я должен решить это? $\text{Max}2\text{Sat}$ $\frac{55}{56}$ $\text{Max}3\text{Sat}$

complexity-theory satisfiability approximation Joni
источник

8

В своей знаменитой статье, Håstad показывает , что она является NP-трудной приблизительным MAX2SAT лучше , чем . Это , вероятно , означает , что это является NP-трудно отличить экземпляры , которые являются & ; выполнима и примеры , которые являются ; выполнимо, для некоторых $21/22$ $\leq \alpha$ $\geq (22/21) \alpha$ . Теперь представьте себедополняя экземпляр таким образомчто он становится группы фракций нового экземпляра, остальная часть которых ровно -satisfiable (скажемсостоит из групп статей вида $\alpha \geq 1/2$ $p$ $1/2$ $a \land \lnot a$ ). Числа теперь становятся и . Последнее число может быть сделано так близко к как мы хотим. $1/2 + p (\alpha - 1/2)$ $1/2 + p((22/21)\alpha - 1/2)$ $1/2$

Юваль Фильмус
источник

Работает ли ваш метод, когда ε - произвольное (но достаточно малое) действительное число? Я не могу понять, как выбрать подходящее количество предложений для заполнения, если я не предполагаю что-то относительно ε. (Обратите внимание, что ε не является частью ввода, и, следовательно, он хорошо определен для рассмотрения действительного числа ε.)

Tsuyoshi Ito

Вот где разрыв между

и

может быть полезным. Предполагая, что

рационально, возьмите некоторое рациональное

, и у вас все получится.

1 / 2 + p (α - 1 / 2)

$1/2+p(\alpha-1/2)$

1 / 2 + p ((22 / 21) α - 1 / 2)

$1/2+p((22/21)\alpha-1/2)$

α

$\alpha$

p

$p$

Юваль Фильмус

Ага, почему-то я думал, что этот метод не работает, когда я попробовал его в первый раз, но теперь я вижу, как он работает. Спасибо!

Цуёси Ито

5

Если вы знаете, что ε - рациональное число, то вам не нужна неприемлемость для Max-2-SAT, чтобы доказать свое утверждение. Типичное доказательство NP-твердости Max-2-SAT (например, в учебном пособии по вычислительной сложности от Papadimitriou) фактически доказывает NP-полноту L _1/5 . Чтобы доказать NP-твердость L _ε для положительных рациональных чисел ε <1/5, мы можем уменьшить L _1/5 до L _ε следующим образом: учитывая формулу 2CNF φ (пример для L _1/5 ), пусть m будет количество статей в нем. Пусть г иs - положительные целые числа, такие что (1 / 5− ε ) mr = 2 ε s . Затем построите формулу 2CNF (экземпляр для L _ε ), повторив φ для r раз и добавив s пар противоречивых предложений. Простой расчет показывает, что это действительно сокращение от L _1/5 до L _ε .

Это сокращение явно работает, только если ε рационально, потому что иначе r и s не могут быть приняты как целые числа. Общий случай, когда ε не обязательно рациональн, кажется, требует неприемлемости, как писал Юваль Фильмус в своем ответе.

Цуёси Ито
источник

Найти

Ответы: