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!

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
0
$\begingroup$

Language C is non-trivial if both C and its complement are non-empty. If A is non-trivial and B is trivial, there cannot be a reduction from A to B.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.