Let \(A \leq _m B\) denotes that language A is mapping reducible (also known…

GATE · 2014 · CS · Set 2 · Computer Science & IT

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.
If $A \leq _m B$ and B is recursive then A is recursive.
B.
If $A \leq _m B$ and A is undecidable then B is undecidable.
C.
If $A \leq _m B$ and B is recursively enumerable then A is recursively enumerable.
D.
If $A \leq _m B$ and B is not recursively enumerable then A is not recursively enumerable.

Attempted by 92 students.

Sign up free to check your answer

Explore the full course: Gate Guidance By Sanchit Sir