p-np - 有哪些 NP 问题可以简化为 NP 完全问题但不能反过来的例子？

Question

有哪些 NP 问题可以简化为 NP 完全问题但不能反过来的例子？当我读到 NP 和 NP-complete 时，我认为映射将是一对一的，因此对它们进行分类是愚蠢的。但是，肯定存在只能在一个方向上还原的问题。我有兴趣了解他们。

Answer 1

所有的 NP 问题都可以简化为 NP 完全问题。NP完全问题是NP问题的一种特殊类型。因此，不需要将NP完全问题归约到NP中；他们已经在NP了。