1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand the meaning, yet regarding formal definitions as I have stated them in the question - I do not see the reason why one cannot just "inverse" reducing function "f". Also, I do not understand why "every decidable problem is reducible to the halting problem, but obviously the halting problem is not reducible to any decidable problem". Cpuld you provide formal definitions? $\endgroup$ – maciek Mar 9 '16 at 19:38
  • $\begingroup$ How exactly would you reverse $f$ ? (I assume were dealing with a computable $f$, otherwise you should provide more context, what reductions are we talking about). Sorry, but these definitions are covered in every computability textbook, or can easily be found on the web. You can study them and come back with more precise questions. $\endgroup$ – Ariel Mar 9 '16 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.