edited by
17,305 views
59 votes
59 votes

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?

  1. If $A\: \leq_m B$ and $B$ is recursive then $A$ is recursive.
  2. If $A\: \leq_m B$ and $A$ is undecidable then $B$ is undecidable.
  3. If $A\: \leq_m B$ and $B$ is recursively enumerable then $A$ is recursively enumerable.
  4. If $A\: \leq_m B$ and $B$ is not recursively enumerable then $A$ is not recursively enumerable.
edited by

4 Answers

Best answer
50 votes
50 votes

$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. 

edited by
45 votes
45 votes

This slide explains everything

3 votes
3 votes
The rules are: If A ≤p B
Rule 1: If B is recursive then A is recursive.
Rule 2: If B is recursively enumerable then A is recursively enumerable.
Rule 3: If A is not recursively enumerable then B is not recursively enumerable.
Rule 4: If A is undecidable then B is undecidable.
Other than these rules, all conclusion are false.

so option (D) is false
0 votes
0 votes
  • A ≤m B means language A is mapping reducible to language B.Thus, 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 three options are correct.
  • As B is not recursively enumerable, it doesn't guarantee A is not recursively enumerable.Thus, if A ≤m B and B is not recursively enumerable then A is not recursively enumerable. Therefore, answer is D is correct
Answer:

Related questions

91 votes
91 votes
5 answers
2
43 votes
43 votes
3 answers
3