如何正式证明或反证如果问题A≤pB，那么得出B≤pA
我直觉上认为应该反驳，但是我不确定该怎么做。
现在，对于问题（M，x），如下创建新问题。令M'为新的TM：每当M停止接受M'时，M'停止接受，每当M停止拒绝时M'进入无限循环。我们的新问题是：给定（M'，x），M'是否在x处停止？
第一个问题的实例可以在多项式时间内转换为第二个问题的实例；第二个问题的解决方案可以在多项式时间内转换回第一个问题的实例。这意味着第一个问题可简化为第二个问题的多项式时间。的确，如果我们有一个解决暂停问题的TM，我们可以使用这种构造来解决多项式开销的多项式成员问题。
现在，停止问题的多项式时间可简化为确定任意决策者M是否接受某些字符串x的问题吗？明显不是。我们可以选择M作为接受偶数长度字符串的TM。然后确定“ M是否接受x？”的时间复杂度。问题大小将是线性的。如果停止问题可以用多项式时间简化，那么停止问题将在P中-显然不是这种情况。]