0
$\begingroup$

I have problems with the basics of mapping reductions.

I can understand how to do reductions using a Turing machine, but without it, I get a little bit confused.

For example:

  1. How do I do a mapping reduction from $a$ to $b$, where $a$ is $\{0,1\}$ and $b$ is $\{0\}$ over the alphabet of $\{0,1\}$?
  2. Does every language have a reduction to itself?
$\endgroup$
0
$\begingroup$

The identity function is a reduction from a language to itself. One reduction from $\{0,1\}$ to $\{0,1\}$ is given by $\lfloor x/2 \rfloor$, which maps $0,1$ to $0$, and all other integers to non-zero values.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I am over the Alphabet of {0,1} so for input x = 000 i need tu return an instance other then 0. tnx $\endgroup$ – aradona Jul 24 '17 at 14:07
  • $\begingroup$ @aradona A suitable reduction would be a function $f$ which is defined to map 0 and 1 to 0 and any other input to 1. $\endgroup$ – Rick Decker Jul 24 '17 at 14:12

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.