1
$\begingroup$

From Sipser,

Language A is mapping reducible to language B, written $A \leq_m B$, if there is a computable function $f : \Sigma^* \rightarrow \Sigma^*$, where for every $w$, $w ∈ A \Leftrightarrow f(w) \in B$. The function $f$ is called the reduction from A to B.

A function is injective if every element in the co-domain is mapped to by at most one element of the domain.

I'm confused on how $w \notin A$ are handled. It seems that for $w \in A$ every element must map to a unique $b \in B$. Because $w \in A \Leftarrow f(w) \in B $.

New question then, is there any use to having an injective reduction? I've noticed that many proofs of NP-hardness seem to have reductions that are injective (at least on $w \in A$). If reductions are not injective ~~ Why don't we simply define our reduction function $R$ as follows, check if $w \in A$, If $w \in A$ then map to a constant $b \in B$. Else, map to a constant $c \notin B$?

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ There's no need for the mapping function to be injective. In fact, it's allowable for all $w\in A$ to map to a single element in $B$ and all of $\overline{A}$ to map to a single element in $\overline{B}$. [For example, this is part of the usual proof that every decidable language (except the trivial ones) is mapping reducible to any other.] $\endgroup$ – Rick Decker Apr 27 '17 at 17:00
  • $\begingroup$ Take the definition literally. $\endgroup$ – Raphael♦ Apr 27 '17 at 18:14
5
$\begingroup$

The function $f$ does not need to be injective. It would be fine to map every $w \in A$ to the same element $w' \in B$ (and to map every $w \in \Sigma^* \setminus A$ to the same $w'' \in \Sigma^* \setminus B$). In fact, for every decidable language $A$, we have $A \leq_m B$ for every $B$ such that $B \neq \Sigma^*$ and $B \neq \emptyset$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Heh. Got in a few seconds before you. +1 anyway $\endgroup$ – Rick Decker Apr 27 '17 at 17:02
  • $\begingroup$ @RickDecker New question then, is there any use to having an injective reduction? I've noticed that many proofs of NP-hardness seem to have reductions that are injective (at least for $w \in A$). If reductions are not injective ~~ Why don't we simply define our reduction function R as follows, check if $w \in A$, If $w \in A$ then map to a constant $b \in B$. Else, map to a constant $c \notin B$? $\endgroup$ – Daniel Apr 27 '17 at 17:21
  • $\begingroup$ The reason you can't do that in the context of NP-hardness proofs is that we have the additional constraint that $f$ is computable in polynomial time. If $A$ is NP-hard you can't check $w \in A$ in poly. time unless P = NP. $\endgroup$ – Pontus Apr 27 '17 at 17:27

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.