Я немного запутался. Я знаю, как уменьшить 3-SAT до IS. Примером преобразования 3-SAT в граф IS может быть создание графа, представляющего каждый пункт 3-SAT, с последующим объединением x и! X и последующей отправкой его в IS. Как бы мы применили это к более общему снижению c SAT <= p IS, не уменьшая SAT до 3-SAT? Мне кажется, что все будет так же, но у меня такое чувство, что я чего-то упускаю. Экземпляр SAT: </p>
x1 ∧ (x2 ∨ ̄x1) ∧ (x3 ∨ x4 ∨ ̄x2)
Можно ли преобразовать это таким же образом, и существует ли общая c последовательность шагов, которая будет использоваться для всех экземпляров SAT? Как мне это доказать?