The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+28 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 (112k points)
edited by | 3.3k views

4 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 (369k points)
edited by

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

@arjun  what is mapping reducable?
+23 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.8k 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?
I also think so c is the answer
0 votes
what is the meaning of A is reducible to B. if it is not given in question then what will be the possible diffrence in answer ??

comment welcomes.
answered by Active (1.4k points)

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

44,455 questions
49,911 answers
65,897 users