我认为答案是否定的，但我在理解问题的方式上遇到了问题。 通俗地说，它本质上是在问，如果问题 x 可以在多项式时间内简化为问题 y，那么 y 也可以在多项式时间内简化为 x，对吧？ 从它是如何使用不等式编写的，它应该是错误的。
如果 X ≤ p Y 在外行人看来，这表明 X 可以在多项式时间内简化为 Y
那么问题是 Y ≤ p X 外行人建议 y 在多项式时间内减少到 X
这个问题让我有点困惑。
最佳答案
我想你的意思是问“X ≤p Y 意味着 Y ≤p X 吗？”。
答案是否定的。例如2-SAT可以很容易地降为3-SAT，但3-SAT不能在P-time降为2-SAT，除非P=NP。
如果 P=NP，答案仍然是否定的。例如，任何 P 时间决策问题都可以简化为停机问题，但停机问题是不可判定的。
关于algorithm - 如果 X ≤ p Y Y ≤ p X 可以吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53753967/