这是一个需要开始的家庭作业问题。在开始之前我还有一些问题。
我们的问题是：
"从k独立集减少到2−SAT如下。给定一个具有n个顶点的图G形成n个命题，每个顶点一个。如果顶点i属于独立集，则顶点i的每个命题xi都设置为真。现在，对于每个边（u，v），写一个子句，说明u和v都不属于独立集。"
我的问题是，我读到的所有东西都说2-SAT不是NP完全问题。那么，我们如何才能从独立集问题中进行约简呢？
找到任何独立集和找到最大独立集（最大大小的独立集）之间有一个重要的区别。
使用您在问题中描述的约简，找到任何独立集都可以很好地简化为2-SAT。这两个问题都不是NP完全问题。请注意，您在问题中描述的缩减不会以任何方式限制独立集中的节点数量。即使是空集也会满足这种约简产生的2-SAT问题，因为空集也是一个独立集！
然而，寻找最大独立集（或k-独立集）是一个NP完全问题。它不会减少到2-SAT。
或者换句话说："k-独立集"中的k是一个额外的约束，它不是2-SAT约简的一部分（这就是为什么在约简的描述中甚至没有提到k+/em>）。您可以在SAT问题中添加额外的子句来计算包含的节点数，并强制要求该数至少为k，但仅添加2个子句是无法做到这一点的。因此，添加k是2-SAT问题成为NP完全一般SAT问题的步骤。
MAX-2-SAT是2-SAT的NP完全扩展，也可以用于使用您发布的约简来解决最大独立集问题。（你需要对归约做两个简单的修改：（1）为每个命题添加1个从句，（2）复制2个从句进行加权。）