我有点困惑。我知道如何将 3-SAT 减少到 IS。将 3-SAT 转换为 IS 图的示例是创建一个表示 3-SAT 的每个子句的图，然后将 x 和 !x 连接起来，然后将其提交给 IS。我们如何将其应用于更通用的 SAT <=p IS 减少，而不将 SAT 减少到 3-SAT？对我来说，这似乎是相同的方式，但我有一种感觉并非如此，我错过了一些东西。SAT的一个例子：
x1 ∧ (x2 ∨ ̄x1) ∧ (x3 ∨ x4 ∨ ̄x2)
我们是否会以同样的方式对其进行转换，是否有一个通用的步骤序列可用于所有 SAT 实例？我将如何证明？