NP、NP-完全、NP-困难问题

Question

我正在学习 NP，我不明白如何解决以下问题。我想知道我应该使用什么策略来解决此类问题。

问题是：

假设 A 和 B 是具体的决策问题，并且 f 是将 A 简化为 B 的多项式时间函数。哪个陈述是正确的，哪个陈述是错误的？

1. 如果 A →f B 且 A Î P，则 B Î P
2. 如果 A →f B 且 B Î NP，则 A Î P
3. 如果 A →f B 且 A 属于 NPC，则 B 属于 NPH
4. 如果 A →f B 且 B 属于 NPC，则 A 属于 NPC
5. 如果 A →f B 且 B →f A，则 A, B ∈ NPC
6. 如果 A →f B 且 B ∈ NPC，则 B →f A
7. 如果 A →f B 且 A Î NPC，则 B Î NPC
8. 如果 A →f B 且 A Î NPH，则 B Î NPC

提前致谢。

Answer 1

• A → B 且 A Î P，则 B Î P => TRUE

• A → B 且 B Î NP，则 A Î P => FALSE

• A → B 且 A Î NP-C，则 B Î NP-H => TRUE

• A → B 且 B Î NP-C，则 A Î NP-C => TRUE

• A → B 且 B ∈ NP-C，则 B → A => TRUE

• A → B 且 A Î NP-C，则 B Î NP-C => FALSE

• A → B 且 A Î NP-H，则 B Î NP-C => FALSE

如果A可以在O(n)时间内减少A -> B并且A是NP-C，你不能保证A是NP-C，因为B是NP-Hard （可能是 NP-C 但你不知道）。

否则，如果 A 可以在 O(n) 时间内约简 A->B 并且 B 是 NP-C，则可以保证 A 是 NP-C。

当您应用多项式时间的减少时，这意味着您正在减少同一类复杂性。

希望对您有帮助！

Answer 2

• 如果 A →f B 且 A Î P，则 B Î P False
• 如果 A →f B 且 B ∈ NP，则 A ∈ P False
• 如果 A →f B 且 A 属于 NPC，则 B 属于 NPH True
• 如果 A →f B 且 B 属于 NPC，则 A 属于 NPC False
• 如果 A →f B 且 B →f A，则 A, B ∈ NPC False
• 如果 A →f B 且 B ∈ NPC，则 B →f A False
• 如果 A →f B 且 A Î NPC，则 B Î NPC False
• 如果 A →f B 且 A Î NPH，则 B Î NPC False

Answer 3

• 如果 A →f B 且 A Î P，则 B Î P False
• 如果 A →f B 且 B ∈ NP，则 A ∈ P False
• 如果 A →f B 且 A Î NPC，则 B Î NPH True， 因为A是NPC，所以NP中的每个问题都可以简化为A，并且由于A可以简化为B，这意味着B是NPH。请记住，如果 NP 中的所有问题都可以归结为 NPH，那么我们称该问题为 NPH。
• 如果 A →f B 且 B ∈ NPC，则 A ∈ NPC False，不一定，因为 A 可以在 NP 中而不在 NPC 中，但仍然可以简化为 NPC，例如 B。
• 如果 A →f B 且 B →f A，则 A, B ∈ NPC False，可能都是 P。
• 如果 A →f B 且 B ∈ NPC，则 B →f A False
• 如果 A →f B 且 A ∈ NPC，则 B ∈ NPC False，因为 A 是 NPC，A 可以简化为 B 意味着 A 是 NPH 不是 NPC，而要成为 NPC，它也必须是 NP。
• 如果 A →f B 且 A Î NPH，则 B Î NPC False