Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From my textbook, I can see that

A language A is mapping reducible to language B if there is a computable function such that for every $w$, $w \in A \Leftrightarrow f(w) \in B$.

Now, what I fail to grasp is on why it isn't just enough to enforce that for every $w$, $w \in A \Rightarrow f(w) \in B$. Intuitively, it seems that this would be enough. With this, we know we can map every element of $A$ onto $B$. Shouldn't this be enough? Why is it not?

I guess the $\Leftarrow$ part must have something to do with not allowing elements outside of $A$ to be mapped onto $B$. Is that it? What would be the problem that would originate?

share|improve this question
    
Arora and Barak give a nice picture of the relationships in Figure 2.1 in their textbook; a draft copy is available here: cs.princeton.edu/theory/complexity/NPchap.pdf –  ShyPerson Jun 7 '11 at 4:21

3 Answers 3

up vote 10 down vote accepted

Let's take $B=\{0\}$. Now define a function $f(w)=0$. This is a reduction satisfying your condition, but it's useless since it can't differentiate elements of $A$ from nonelements of $A$, which is the whole point of reductions.

In reductions we try to move from the problem of deciding if something is in A, to deciding if something is in B. With a reduction we are able to say "if it's in B, the original was in A; and if it is not in B, the original was not in A". Your type of reduction enables us to say only the second statement, not the first.

share|improve this answer

Gadi A has the right answer, but I want to point out that things go spectacularly wrong without the "if and only if". Suppose that $B$ has any element $b$ and let $f_b$ be the function such that $f_b(n) = b$ for all $n$. Then $f_b$ would be a reduction in your weaker sense from any set $A$ to the set $B$. So, in particular, any two nonempty sets would be reducible to each other in the weaker form of "reducibility".

share|improve this answer
    
This is a strong point; I tried to give it myself in my $B=\{0\}$ example but you give a better emphesis. –  Gadi A Jun 4 '11 at 11:55

The word problem for groups was shown unsolvable by (computably) associating to each Turing machine $M$ a finitely presented group $G_{M}$ such that $M$ halts on input word $w$ if and only if $w$ is equivalent to the identity in $G_{M}$. More precisely, let $A_{\text{TM}}$ be the accepting language for Turing machines (also known as the halting set) and let $\text{Ident}$ be the language of words $\langle{G,w}\rangle$ such that $w$ is equivalent to the identity in the group $G$. A computable function $f: A_{\text{TM}} \to \text{Ident}$ was constructed so that $\langle{M,w}\rangle \in A_{\text{TM}}$ $\Longleftrightarrow$ $f(\langle{M, w}\rangle) \in \text{Ident}$. Thus to decide if machine $M$ accepts input $w$ (i.e. if $\langle{M,w}\rangle \in A_{\text{TM}}$), it suffices to compute $f(\langle{M,w}\rangle)$ and decide if that is in $\text{Ident}$. But $A_{\text{TM}}$ is undecidable, so $\text{Ident}$ must also be.

However, this argument wouldn't work if we only had $\langle{M,w}\rangle \in A_{\text{TM}}$ $\Longrightarrow$ $f(\langle{M, w}\rangle) \in \text{Ident}$, because then, as Gadi and Carl pointed out, even if we could decide if $f(\langle{M,w}\rangle) \in \text{Ident}$, it would give us no information about whether or not $\langle{M,w}\rangle \in A_{\text{TM}}$ because in the case where $f(\langle{M,w}\rangle) \in \text{Ident}$ holds, we could still have $\langle{M,w}\rangle \notin A_{\text{TM}}$.

It is worth noting that, conversely, if we only had $\langle{M,w}\rangle \in A_{\text{TM}}$ $\Longleftarrow$ $f(\langle{M, w}\rangle) = \langle{G, w}\rangle \in \text{Ident}$, the case where $f(\langle{M,w}\rangle) \notin \text{Ident}$ gives no information.

share|improve this answer
    
Why go as far as the word problem? What's wrong with the Halting problem, or simply saying "even undecidable languages can be reduced to a decidable language with you reduction type"? –  Gadi A Jun 4 '11 at 15:39
    
@Gadi I think it's instructive to show a reduction in the "real-world". What do you mean by "What's wrong with the Halting problem..."? Are you intending to reduce the Halting problem to something else? If so, what? –  Quinn Culver Jun 5 '11 at 4:08
    
I meant, what's wrong with reducing HP to something trivial, like you reduced WP to something trivial. Also, I think of HP as quite "real-world"-like, since it deals with the concrete question whether some computer program will stop or not. –  Gadi A Jun 5 '11 at 4:21
    
What is something "trivial" that you would reduce HP to? I didn't "reduce WP to something trivial". Rather, I reduced HP to WP. I agree that HP is "real-world", but typically it is the set which is shown to be $m$-below others. –  Quinn Culver Jun 5 '11 at 14:22
    
What I meant was - as a counterexample to devoured elysium's reduction type you can show that HP is reducible (by this reduction type) to a language of size 1. –  Gadi A Jun 5 '11 at 16:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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