1
$\begingroup$

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!

$\endgroup$

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.