computer-science - 如果一个问题 A ≤p B，那么 B ≤p A，证明或反证

Question

如何正式证明或反证如果一个问题 A ≤p B，那么 B ≤p A

我凭直觉认为这应该被反驳，但我不知道该怎么做。

Answer 1

考虑以下问题：给定一个判定器 M 和一个字符串 x，确定 M 是否接受 x。因为 M 是一个决策者，我们总是可以在 x 上运行 M 来得到我们的答案。这的时间复杂度完全取决于语言 M 决定什么以及它是如何决定的。

现在，对于问题 (M, x)，创建一个新问题，如下所示。设 M' 是一个新的 TM：每当 M 停止接受时，M' 停止接受，而每当 M 停止拒绝时，M' 进入无限循环。我们的新问题是：给定 (M', x)，M' 会在 x 上停止吗？

第一个问题的实例可以在多项式时间内转换为第二个问题的实例；第二个问题的解决方案可以在多项式时间内转换回第一个问题的实例。这意味着第一个问题可以多项式时间简化为第二个问题。事实上，如果我们有一个解决停机问题的 TM，我们可以使用这种结构来解决具有多项式开销的每个成员问题。

现在，停止问题多项式时间是否可以简化为确定任意决策器 M 是否接受某个字符串 x 的问题？明显不是。我们可以选择 M 作为接受偶数长度字符串的 TM。然后是决定“M 是否接受 x？”的时间复杂度。问题大小是线性的。如果停止问题是多项式时间可简化为此，那么停止问题将在 P 中 - 显然不是这种情况。