Np类的问题

Question

是否已知NP中的所有问题都可以相互减少。我知道问题X是否在NP中，并且NP中的任何NP问题Y可以简化为X然后X是NP完全的。那么通过这个假设，我们可以说所有NP问题都可以相互减少吗？

Answer 1

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参考下面的图像以便更好地理解。

Answer 2

不，并非NP中的所有问题都可以相互减少。 NP中的某些东西与NP难的东西不同。如果某些东西在NP中并且是NP难的，那么它被称为NP-complete。要在NP中，需要能够在多项式时间内验证问题。 NP难问题是在已知算法下被认为不可能有效解决的问题。要成为NP难，一个问题需要能够被解决为另一个NP难的问题。如果X和Y都在NP中（就像你的例子那样）那么Y可以简化为X，这并不意味着Y或X都是NP难的，因为它们都没有被简化为现有的NP难问题。