Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$. Which one of the following is FALSE?
$A \leq_m B$ means $A$ cannot be harder than $B$. (Since $A$ can be reduced to $B$, instead of deciding $A$, we can now decide $B$)
So, the first 3 options are correct. Option (D) is false, as $B$ is not recursively enumerable doesn't guarantee $A$ is not recursively enumerable.
A ≤m B implies that B is atleast as hard as A .
If B is easy then A is easy
If A is hard then B is hard
If B is hard then A may or may not be hard (Because B being hard does not garuntee A being hard)
If A is easy then B may or may not be easy (Because A being easy does not garuntee B being easy)
@ Arjun sir ,
can you explain a bit more detailed way pls
i didn't get why the first three options are correct
thanks in advance
This slide explains everything
What significance does this line holds in this...
First of all, congratulations!