NP问题之间的减少

Question

根据定义，NP 中的任何问题都可以简化为 NP-Complete 中的问题。但是，假设我们在 NP 中有两个任意问题 X 和 Y。 X 可还原为 Y 是否必然为真？

我不清楚两个具有特定复杂性的任意问题之间的减少方面class，因此任何指导将不胜感激。

Answer 1

原则上，没有理由可以将一个任意问题简化为另一个问题。

举个具体的例子，已知n位任意整数的因式分解在NP，但据信不在P和不 NP- 完整。因此旅行商不能还原为整数分解。

https://en.wikipedia.org/wiki/NP-intermediate 列出了属于同一类别的其他问题，没有理由相信，例如，图同构可归约为因式分解，反之亦然。