Поли-тайм сокращение от ILP до SAT?

14

Итак, как известно, проблема решения ILP 0-1 является NP-полной. Показать его в NP легко, а оригинальное сокращение было от SAT; с тех пор было доказано, что многие другие проблемы NP-Complete имеют составы ILP (которые функционируют как сокращение от этих проблем до ILP), потому что ILP очень полезен.

Сокращения от ILP кажутся намного труднее или сделать самостоятельно или отследить.

Таким образом, мой вопрос: знает ли кто-нибудь сокращение временного интервала от ILP до SAT, то есть демонстрирует, как решить любую проблему решения 0-1 ILP с использованием SAT?

codetaku
источник

Ответы:

12

0-1 ILP сформулирован как:

Существует ли вектор учетом ограничений:x

a11x1+a12x2...+a1nxnb1a21x1+a22x2...+a2nxnb2...am1x1+am2x2...+amnxnbm

xjxxj{0,1}

Сокращение до k-sat:

Сначала приведите к схеме сб:

a1jxjb1

b1

a1jb1

xj

Окончательный CNF будет содержать все ограничения.

Реал Слав
источник
Ах, теперь я вижу ... Я как-то забыл про вариант прохождения трассы села .... Большое спасибо за вашу помощь.
codetaku
0

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

Представьте, что у вас есть одно из неравенств:

5*Икс1+2*Икс2+3*Икс36

(1,1,1)(1,1,0)(1,0,1)

(1,1,1)¬(x1x2x3)(¬x1¬x2¬x3)

(¬x1¬x2¬x3)(¬x1¬x2x3)(¬x1x2¬x3)

Обойдя все неравенства и собрав пункты, вы получите cnf в конце. Часто этот cnf будет ПУТЬ ПРОСТО, а затем тот, который следует из принятого ответа. Стоимость предварительной обработки сложнее, хотя.

Константин Владимиров
источник