If a problem A ≤p B, then that B ≤p A, prove or disprove

Question

How to formally prove or disprove that if a problem A ≤p B, then it follows that B ≤p A

I intuitively think this should be disproved, but I'm not sure how to go about it.

Answer 1

Consider the following problem: given a decider M and a string x, determine whether M accepts x. Because M is a decider, we can always just run M on x to get our answer. The time complexity of this depends entirely on what language M decides and how it decides it.

Now, for the problem (M, x), create a new problem as follows. Let M' be a new TM: M' halt-accepts whenever M halt-accepts, and M' goes into an infinite loop whenever M halt-rejects. Our new problem is this: given (M', x), does M' halt on x?

An instance of the first problem can be transformed in polynomial time to an instance of the second problem; and a solution to the second problem can be transformed in polynomial time back to an instance of the first problem. This means the first problem is polynomial-time reducible to the second problem. Indeed, if we had a TM that solved the halting problem, we could use this construction to solve every membership problem with polynomial overhead.

Now, is the halting problem polynomial-time reducible to the problem of deciding whether an arbitrary decider M accepts some string x? Obviously not. We could choose M to be a TM that accepts strings of even length. Then the time complexity of deciding "does M accept x?" would be linear in the problem size. If the halting problem were polynomial-time reducible to this, then the halting problem would be in P - clearly not the case.