Reduction between two decision problems

Question

We are given two decision problems: $Q_1\colon I_1\to\{0,1\}$ and $Q_2\colon I_2\to\{0,1\}$.

By definition, if there exists a function $f\colon I_1\to I_2$ such that for each $x\in I_1$ we have $Q_1(x)=Q_2(f(x))$ then $Q_1$ can be reduced to $Q_2$ by $f$.

Now suppose that $Q_1$ can be reduced to $Q_2$ by a given $f$. My question is: is that true, that there always exists a function $g\colon I_2\to I_1$ such that for each $y\in I_2$ we have $Q_2(y)=Q_1(g(y))$?

I believe so. Since the reduction of $Q_1$ to $Q_2$ by $f$ can be executed in a finite number of well-described steps and since I know explicitly the mapping: $I_1\to I_2$ I think there has to be a way to "reverse" the operation of reduction. Am I right? Is there a formal proof?

Answer 1

First, your definition of reducibility needs to include some sort of restriction on the power of $f$: typically, for example, we require the function to be computable.

Without this restriction, any two decision problems (except the trivial problems "always yes" and "always no") are reducible to each other. Since there are always $y$ and $n$ such that $Q_2(y)=1$ and $Q_2(n)=0$, there is always a function $f$ that reduces $Q_1$ to $Q_2$: just take \begin{equation*} f(x) = \begin{cases} \ y &\text{if }Q_1(x)=1\\ \ n &\text{if }Q_1(x)=0\,. \end{cases} \end{equation*}

So, we typically restrict to computable functions $f$ as reductions. Your question is, essentially, is a computable reduction always reversible? The answer to this is no and the reduction $f$ above gives a big hint why: that function is not invertible and there's no reason, in general, to expect that even a computable reduction should be invertible.

For example, consider any decidable problem $Q_1$, and let $Q_2$ be the halting problem. In this case, we can take $y$ to be the description of any Turing machine that halts immediately, and let $n$ be any Turing machine that just moves the head right forever. Since $Q_1$ is decidable, the reduction $f$ above is computable. It tells you how to translate questions about $Q_1$ to questions about the halting problem. It also kind of tells you how to translate questions about whether or not $y$ and $n$ halt into questions about $Q_1$. But it doesn't help you determine whether any other Turing machine halts – and it can't, because that problem is undecidable.

Answer 2

No, you cant always find a reverse reduction. If $A$ is reducible to $B$ you should read it as: $A$ is not harder than $B$ (if i can decide membership to $B$, then i can decide membership to $A$), nothing is said about the opposite. For example, every decidable problem is reducible to the halting problem, but obviously the halting problem is not reducible to any decidable problem.