Problem Detail: 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, wrangle 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?
Asked By : Iancovici
Answered By : Luke Mathieson
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:
- $x in A Leftrightarrow g(f(x)) in C$.
- $fcdot 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)$?)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11536
