algorithm - 3-SAT 多项式等价于 INDEPENDENT-SET

Question

我知道 3-SAT 可以多项式简化为 INDEPENDENT-SET 问题。现在是 INDEPENDENT-SET 问题多项式可简化为 3-SAT 问题吗？那么这些问题是多项式等价的吗？

我认为是这样，因为根据我的观点，INDEPENDENT-SET 问题的每个实例都可以用 3-SAT 表示（在某些情况下，在添加一些额外的边之后）。但是我不清楚我的这种理解。

请帮帮我。

Answer 1

是的，独立集问题可以在多项式时间内简化为 3SAT。决策问题“给定一个图 G 和数字 k，在 G 中是否存在一个大小至少为 k 的独立集？” 在 NP 中（你明白为什么吗？）。由于 3SAT 是 NP 完全的，所以 NP 中的所有问题都是多项式时间可约化为它的，因此独立集问题可约化为它。

希望这可以帮助！