complexity-theory - 如果 A 是 NP 完全的并且如果从 A 减少到 B，是否意味着 B 也是 NP 完全的？

Question

已结束。此问题不符合 Stack Overflow guidelines .它目前不接受答案。

---

这个问题似乎与 help center 中定义的范围内的编程无关。 .

关闭 8 年前。

Improve this question

假设 A、B 和 C 是决策问题。还假设 A 是多项式时间可约化为 B 且 B 是多项式时间可约化为 C。如果 A 和 C 都是 NP-完全的，那么这是否意味着 B 也是 NP-完全的？

我知道，如果 A 是 NP 完全的并且它是多项式时间可约化为 B，那么 B 是 NP 难的。但是，为了使问题成为 NP 完全问题，它必须满足 (1) 它在 NP 中，并且 (2) 它是 NP-hard。

我不知道如何证明 NP-complete 的第一个要求。

Answer 1

如果 A 是 NP 完全的，并且多项式时间可简化为 B，则 B 是 NP-hard。

如果 B 是多项式时间可约简为 C 且 C 是 NP 完全的，则 B 在 NP 中。

NP-hard 中的一个 NP 问题是 NP-complete。

另一种证明 B 是 NP 完全问题的方法是注意任何两个 NP 完全问题(例如 A 和 C)彼此是多项式可约化的，因此 B 等价于(双向多项式可约化)任何 NP - 完整的问题。