1
$\begingroup$

How can we prove that $h(x) = g(f(x))$ is a reduction function for $A \leq_m C$,

if $f$ is the reduction function of $A \leq_m B$ and $g$ is the reduction function for $B \leq_m C$

The given Proposition is: $A \leq_m B, B \leq_m C \Rightarrow A \leq_m C$

I was thinking about using $HALT_{TM}$ for A. So on input $\langle M, w\rangle \in A$ if and only if $\langle M'',w'' \rangle \in C$

The output of A would be $ \langle M', w' \rangle$ and the output of B would be $\langle M'',w'' \rangle$

If the constructed $M$ rejects the input $x$, then it loops forever, so $C$ is not recursive if $A$ is not recursive

If this isn't sufficient, then what am I missing?

$\endgroup$
  • 3
    $\begingroup$ Unfold the definitions ... $\endgroup$ – Dave Clarke Apr 24 '13 at 12:37
  • 1
    $\begingroup$ This tastes like homework. What have you tried? $\endgroup$ – Raphael Apr 24 '13 at 17:44
5
$\begingroup$

The properties that reductions have are:

  • They preserve language membership (or Yes-instances, or whichever phrasing you prefer).
  • They are computable.

So then given that you have two reductions $f$, which takes instances of $A$ and produces instances of $B$ such that $x \in A \Leftrightarrow f(x) \in B$, and $g$ which does the same for $B$ and $C$, you need to show:

  1. $x \in A \Leftrightarrow g(f(x)) \in C$.
  2. $f\cdot g$ is computable.

The first should be a fairly straightforward application of basic logic. The second is also easy.

You can't just take $A=HALT_{TM}$ though, as all you would show then is that $HALT_{TM} \leq_{m} C$, whereas your question (appears) to ask for a proof of the transitivity of many-one reductions in general. (As a comparison would showing that $(10^{100} < b) \wedge (b <c) \Rightarrow (10^{100} < c)$ show that $(a < b) \wedge (b <c) \Rightarrow (a < c)$?)

$\endgroup$

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.