如果 X ≤ p Y Y ≤ p X 可以吗？
If X ≤p Y can Y ≤p X?
我认为答案是否定的，但我在理解问题的方式上遇到了问题。
通俗地说，它本质上是在问，如果问题 x 可以在多项式时间内简化为问题 y，那么 y 也可以在多项式时间内简化为 x，对吧？
从它是如何使用不等式编写的，它应该是错误的。
如果外行人 X ≤ p Y，这表明 X 可以在多项式时间内减少到 Y
问题是 Y ≤p X 外行人建议 y 在多项式时间内减少到 X
这个问题让我有点困惑。
答案：
所以我们有 X ≤p Y。你问的是，有没有可能 Y ≤p X?
考虑一下：如果 X 和 Y 是同一个问题怎么办？然后，平凡地，X 可以在多项式时间内简化为自身（仅通过原始问题实例），所以我们有 X ≤p Y。但随后它遵循相同的论点 Y ≤p X!
因此我们找到了一个例子 X ≤p Y 和 Y ≤p X 所以你的问题的答案是肯定的。
（然而，任何问题 X 和 Y 都可以在多项式时间内以两种方式减少，这当然 不是 正确。）
类似于整数：
正如您在问题中似乎也指出的那样，≤p 与正常不等式 ≤ 之间肯定存在一些相似之处，例如整数：说 a ≤ b。那么 b ≤ a 是真的吗？嗯，是！每当 a = b.
在计算问题的上下文中，两个问题 X 和 Y 不必完全相同就可以在两个方向上进行简化。 （总是很容易找到两个相同的问题，但只是为了一些任意的细节。）
例如（在更高层次上），在整数数组中找到 最大 值的问题可以很容易地简化为找到 [=46] 的问题=]smallest（通过简单地否定所有元素）。然后，我们还可以将寻找 最小 整数的问题简化为寻找 最大 的问题（通过简单地再次求反）。
我想你是想问"Does X ≤p Y imply that Y ≤p X ?"。
答案是否定的。例如2-SAT可以很容易地减少到3-SAT，但是3-SAT不能在P时间减少到2-SAT，除非P=NP。
如果P=NP，答案仍然是否定的。例如，任何 P 时间决策问题都可以简化为停机问题，但停机问题是不可判定的。
我认为答案是否定的，但我在理解问题的方式上遇到了问题。 通俗地说，它本质上是在问，如果问题 x 可以在多项式时间内简化为问题 y，那么 y 也可以在多项式时间内简化为 x，对吧？ 从它是如何使用不等式编写的，它应该是错误的。
如果外行人 X ≤ p Y，这表明 X 可以在多项式时间内减少到 Y
问题是 Y ≤p X 外行人建议 y 在多项式时间内减少到 X
这个问题让我有点困惑。
答案：
所以我们有 X ≤p Y。你问的是，有没有可能 Y ≤p X?
考虑一下：如果 X 和 Y 是同一个问题怎么办？然后，平凡地，X 可以在多项式时间内简化为自身（仅通过原始问题实例），所以我们有 X ≤p Y。但随后它遵循相同的论点 Y ≤p X!
因此我们找到了一个例子 X ≤p Y 和 Y ≤p X 所以你的问题的答案是肯定的。
（然而，任何问题 X 和 Y 都可以在多项式时间内以两种方式减少，这当然 不是 正确。）
类似于整数：
正如您在问题中似乎也指出的那样，≤p 与正常不等式 ≤ 之间肯定存在一些相似之处，例如整数：说 a ≤ b。那么 b ≤ a 是真的吗？嗯，是！每当 a = b.
在计算问题的上下文中，两个问题 X 和 Y 不必完全相同就可以在两个方向上进行简化。 （总是很容易找到两个相同的问题，但只是为了一些任意的细节。）
例如（在更高层次上），在整数数组中找到 最大 值的问题可以很容易地简化为找到 [=46] 的问题=]smallest（通过简单地否定所有元素）。然后，我们还可以将寻找 最小 整数的问题简化为寻找 最大 的问题（通过简单地再次求反）。
我想你是想问"Does X ≤p Y imply that Y ≤p X ?"。
答案是否定的。例如2-SAT可以很容易地减少到3-SAT，但是3-SAT不能在P时间减少到2-SAT，除非P=NP。
如果P=NP，答案仍然是否定的。例如，任何 P 时间决策问题都可以简化为停机问题，但停机问题是不可判定的。