The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
3.3k views

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
+2

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)

0
here undecidable is superset of decidable.

that is why B) is correct option,

right?
0
@srestha  can u explain 2nd option if A is undecidable how can we say be is also undecidable .
0
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
0
RE IS SEMIDECIDABLE  ?

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
+1
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
+1
thanx
0
@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...
0

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

0
@arjun  what is mapping reducable?
+23 votes

This slide explains everything

answered by Active (2.3k points)
0
is this figure explanation right?
0
Ya bro
0
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)
+1
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?
0
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)
Answer:

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
165,377 comments
65,897 users