The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 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.
asked in Theory of Computation by Veteran (103k points)
edited by | 3k views

3 Answers

+28 votes
Best answer

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

answered by Veteran (359k points)
edited by
Also if B is not recursive then we cant say that A is not recursive....?
yes. We can't.
Can we say that if B is Undecidable then A is also Undecidable ?
is recursively enumerable and undecidable same??
why?? cany anyone explain??
RE and undecidability are not same. RE implies semidecidable. A semidecidable problem could be: a decidable problem if its complement is also semidecidable or it can be undecidable if it's complement is not semidecidable. Undecidable languages are not recursive languages, but sometimes, they may be recursively enumerable languages. (Think complement of halting problem, it is non re and undecideable). Hope this helps.
Do you have the answer to your question now? I too have this confusio. Please help.

Please help me understand this kind of ques: 
For the given ques., If we say that "undecidibility", "not recursive" and "not RE", etc., are the negetive characteristics and opposite of it is positive characteristic for a language, and "A <m B" means that B is more harder than A,
then, can it be a sort of rule that to prove negetive characteristic, A should be known and B becomes the same, and for positive B should be known and A becomes the same.

for eg. if A <m B and A is undecidable then B is undecidable. (negetive)
If A ≤m B and B is recursively enumerable then A is recursively enumerable.(positive)

similerly, If A ≤m B and B is not recursively enumerable then it doesnt guarantee that A is not recursively enumerable, as we had to prove a negetive characteristic but instead of A, B was known.

Please tell me if it works in general or not.
Also positive - negetive is used just for differentiating.


I tried to make out some analogy, don't know if its correct.

For  L≤mM 


when I read it first, I thought its perfect. But later I found something is odd here. Out of 4 observations which you have made in each category, first two seems to be going good with the venn dig. but when it comes to 3rd and 4th, I think we need to change the representation may be.

if L is recursive then M may or may not be recursive. This makes sense because there is RE language which may not be recursive.------- (case 1)

if L is RE then M may or may not be RE. this also make sense because set of languages is bigger than set of RE languages.

if L is decidable then M may or may not be decidable. How is that possible. M is a bigger set. If it is decidable, then how can anything inside this set can be undecidable. that means, if L is decidable then M can not be undecidable, so the other option left is decidable. In case 1 recursive languages are also RE, but here a decidable language can not be undecidable at the same time.

similerly with 4th observation:

if M is not recursive then L may or may not be recursive. this looks right because here M could be RE and so L can also be RE, but not recursive.

if M is not RE then L may or may not be RE, again doesnt look good for same reason as described above. L is inner entity of M.

if M is not decidable then L may or may not be decidable. if M is not decidable and suppose L is decidable, then L is both decidable and undecidable at the same time.

But about your analogy regarding addition and multiplication, I cant really comment on it. It looks correct to me, but only if we dont represent it via venn diagram. I think if we consider that multiplication is made up of many additions, that is multiplication is derived from addition, then your analogy may suit it.

Let me know what do you think about it.


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)

here undecidable is superset of decidable.

that is why B) is correct option,

@srestha  can u explain 2nd option if A is undecidable how can we say be is also undecidable .
A reducible to B means A atmost as hard as B

Now A is undecidable, means A is RE, Then B must be atleast RE

AND IN SIMILAR MANNER  B IS NOT RE  BUT IT CAN BE OUTSIDE RE SO HOW CAN WE SAY A is not re we can reduce re to  non re
yes semidecidable

Here, RE to Non RE conversion is not needed

RE to RE and Non RE to Non RE conversion needed

Read question once more
@Arjun sir, Why is D false, could you tell the reason? Also how does this work in general, for recursive,RE, NP,NPC and so on, i.e. if A is reducible to B and B is NP then is A NP? and so on...

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

+20 votes

This slide explains everything

answered by Active (2.3k points)
is this figure explanation right?
Ya bro
Excellent explaination.
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
answered by Loyal (8.5k points)
How is option C true? If B is recursively enumerable, A can be either recursively enumerable or recursive. How can A be definitely recursively enumerable?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,078 questions
47,675 answers
62,393 users