So I understand what a mapping reduction is and how to create them for simpler problems such as a reduction from the set of even numbers to set of odd numbers however, seemingly more complicated questions trip me up such as the following...

A and B are computable languages where B is non trivial give a mapping reduction from A to B.

So my thought process with this question is that the reduction must have something to do with the fact that B is non trivial, but I'm not sure.

Any help understanding mapping reductions and this question would be appreciated!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.