The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
3.9k 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 (115k points)
edited by | 3.9k views

4 Answers

+30 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 (384k points)
edited by
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?
0
Please explain your answer......
0

@ravee_rocks I have a small problem.

That is if M is RE then L is RE .

But here L also can be Recursive.

please explain this

0
Yes. You are right. If M is RE then L 'can' be recursive. But it's not mandatory, but If M is RE then L 'must' be RE.

PS: All Recursive languages are RE.
+25 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 (9.3k 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.9k points)
0

@Shubham Aggarwal 

convert your answer to comment.

go to edit and convert it.

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
47,923 questions
52,325 answers
182,358 comments
67,782 users