I find it hard to find reductions that only work on one side: A is mapping reducible to B, but B is not mapping reducible to A. what could be an easy way to find such two languages A,B ? I tried Atm,Htm,EQtm,Etm,RegTm, and many others, and whenever I found that A is reducable to B, I also found that B is reducable to A.


  • 1
    $\begingroup$ Use $\emptyset$ as one of your languages. $\endgroup$ – Yuval Filmus Feb 21 '18 at 9:39
  • $\begingroup$ Perhaps you could answer your own question now? $\endgroup$ – Yuval Filmus Feb 21 '18 at 14:39

I now understand that there is a mapping reduction from the empty language to any other language except Sigma*, and there cannot be a reduction from a language to the empty language except for a reduction from the empty language to the empty language.

| cite | improve this answer | |

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.