Почти 2-SAT NP-жесткий?

10

Сложна ли задача NPF SAT NP, когда общее число (но не ширина) предложений из 3 или более членов ограничено сверху константой? А что конкретно, когда есть только один такой пункт?

np-hardness sat upper-bounds dspyz
источник

8

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

c

$c$

P

$P$

c

$c$

n

$n$

n

$n$

c

$c$

O (n^{2})

$O(n^2)$

n

$n$

Кайл Джонс

@KyleJones Но одно предложение с литералами имеет удовлетворяющих назначений, а не только . Поскольку не ограничено в вопросе, этот подход дает алгоритм экспоненциального времени.

k

$k$

2^{k} - 1

$2^k-1$

k

$k$

k

$k$

Дэвид Ричерби

2

@DavidRicherby Чтобы удовлетворить предложению, вам нужно, чтобы только один из литералов оценивал значение true. После этого предложение можно игнорировать, и у вас остается только формула 2-SAT. литералов означает, что вам нужно только попробовать назначений.

k

$k$

k

$k$

Кайл Джонс

14

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

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

Напротив, если среднее число литералов в предложении составляет не менее для некоторого фиксированного (но сколь угодно малого) , то проблема NP-трудна. $2 + \epsilon$ $\epsilon > 0$

Это можно показать, сократив 3SAT до этой проблемы, введя новые предложения с двумя литералами, которые тривиально выполнимы. Предположим, в экземпляре 3SAT есть предложений; чтобы уменьшить средний размер предложения до , достаточно добавить новых предложений с двумя литералами. Поскольку фиксирован и положителен, новый экземпляр имеет полиномиальный размер. $m$ $(2+\epsilon)$ $m(1 - \epsilon)/\epsilon$ $\epsilon$

Это сокращение также показывает, что даже версия, в которой «большие» предложения ограничены 3 литералами, является NP-сложной.

Оставшийся случай - это когда несколько больших предложений не имеют ограниченного размера; Кажется, что каждый большой пункт усугубляет проблему. См. Статью SODA 2010 Pǎtraşcu и Williams для случая двух предложений: они утверждают, что, если это можно сделать за субквадратичное время, то у нас будут лучшие алгоритмы для SAT. Их аргумент может быть расширен до большего числа предложений, что обеспечит доказательство того, что ваша верхняя граница не может быть улучшена (по модулю некоторой формы гипотезы об экспоненциальном времени).

Андраш Саламон
источник

только косвенно связаны, но есть недавний документ ECCC, который формулирует «почти 2-SAT» по-другому и доказывает сильную твердость: eccc.hpi-web.de/report/2013/159

Сашо Николов

8

Ладно, я понял. Ответ - нет. Это можно решить за многократное время. Для каждого предложения «3 или более» выберите литерал и задайте для него значение «истина». Затем решите оставшуюся проблему 2-sat. Если кто-то предоставляет решение, то это решение общей проблемы. Так как количество предложений с 3 и более членами является фиксированным (скажем, c), то, если все такие предложения имеют размер <= m, то это выполняется в O (m ^ (c) * n). O (m ^ c) для прохождения каждого возможного выбора, времена O (n) для решения оставшейся задачи 2-sat.

dspyz
источник

Но вопрос явно говорит о том, что не ограничено, так что это не алгоритм за полиномиальное время.

m

$m$

Дэвид Ричерби

Это потому, что m неявно ограничено числом атомов. Очевидно, что в предложении не может быть больше литералов, чем атомов в задаче. Возможно, я должен был уточнить m <= n

dspyz

Почти 2-SAT NP-жесткий?

Ответы: