If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that there might be some encodings of L2 that cannot be derived from this reduction.

If such encodings exists in my reduction (the ones in L2 that cannot be gotten from a many reduction from L1), does that many-one reduction still hold valid?

For example (and perhaps this is a terrible example), I want to prove that all odd numbers between 10 and 100 can be many reduced to even numbers and I use a function f: Z -> Z that simply takes a odd x and adds 1 to it. Now, there are still a myriad of even numbers that our reduction from odd numbers did not cover. Can I still say that my reduction is valid this way.

If you need me to make it any clearer, please leave a comment.



Your Answer

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