NP完整性和硬度分类

Question

选择正确的说法：

• (A) 如果X是一个NP完全问题，那么X是一个NP问题
• (B) 如果 X 是一个 NP 完全问题，那么 X 是一个 NP-hard
• (C) 让 X 成为一个 NP 完全问题。如果 X 可以多项式化简为一个问题 Y，那么 Y 是一个 NP-complete。
• (D) 设X 为NP 完全问题。如果 Y 可以多项式化简为一个问题 X，那么 Y 是一个 NP-complete。
• (E) 让 X 成为一个 NP 完全问题。如果 X 可以多项式化简为一个问题 Y，那么 Y 是一个 NP-hard。

我的答案是 (A)(B)(C)(E):

• (A)(B) : X属于NP-complete，表示X属于NP和NP-hard
• (C) 真
• (D) Y 可能是 P、NP-hard 或 NP-complete
• (E) Y是一个NP-complete，也是一个NP-hard

---

答案是否正确？

Answer 1

这里有一些更正：

(C) 错误。 Y 是 NP-hard，但不一定在 NP 中。

(D) 错误。 Y在NP中，不一定是NP完全的。

(E) 正确，但 Y 不一定是 NP 完全的。