Np class 个问题
Np class of problems
是否已知 NP 中的所有问题都可以相互归约。
我知道如果问题 X 在 NP 中并且 NP 中的任何 NP 问题 Y 都可以还原为 X 那么 X 是 NP-complete。那么通过这个假设我们可以说所有 NP 问题都可以相互归约吗？
A decision problem C is NP-complete if:
C is in NP, and
Every problem in NP is reducible to C in polynomial time.
来源：https://en.wikipedia.org/wiki/NP-completeness
如果所有的 NP 问题都可以相互归约，那就意味着所有的 NP 问题都是 NP 完全的，我们不能说，因为我们仍然无法证明是否 P = NP
请参阅下图以更好地理解。
不，并非 NP 中的所有问题都可以相互归约。 NP 中的东西不同于 NP-hard 中的东西。如果某些东西属于 NP 并且是 NP-hard，则它被称为 NP-complete。要在 NP 中，问题需要能够在多项式时间内得到验证。 NP-hard 问题是公认的在已知算法下不可能有效解决的问题。要成为 NP-hard，一个问题需要能够简化为另一个 NP-hard 问题。如果 X 和 Y 都在 NP 中（如您的示例），那么 Y 可还原为 X，这并不意味着 Y 或 X 是 NP-hard，因为两者都没有还原为现有的 NP-hard 问题。
是否已知 NP 中的所有问题都可以相互归约。 我知道如果问题 X 在 NP 中并且 NP 中的任何 NP 问题 Y 都可以还原为 X 那么 X 是 NP-complete。那么通过这个假设我们可以说所有 NP 问题都可以相互归约吗？
A decision problem C is NP-complete if:
C is in NP, and
Every problem in NP is reducible to C in polynomial time.
来源：https://en.wikipedia.org/wiki/NP-completeness
如果所有的 NP 问题都可以相互归约，那就意味着所有的 NP 问题都是 NP 完全的，我们不能说，因为我们仍然无法证明是否 P = NP
请参阅下图以更好地理解。
不，并非 NP 中的所有问题都可以相互归约。 NP 中的东西不同于 NP-hard 中的东西。如果某些东西属于 NP 并且是 NP-hard，则它被称为 NP-complete。要在 NP 中，问题需要能够在多项式时间内得到验证。 NP-hard 问题是公认的在已知算法下不可能有效解决的问题。要成为 NP-hard，一个问题需要能够简化为另一个 NP-hard 问题。如果 X 和 Y 都在 NP 中（如您的示例），那么 Y 可还原为 X，这并不意味着 Y 或 X 是 NP-hard，因为两者都没有还原为现有的 NP-hard 问题。