4k 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.
edited | 4k views

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

+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

0
@arjun  what is mapping reducable?
0
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.

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.

This slide explains everything

0
is this figure explanation right?
0
Ya bro
0
Excellent explaination.
• 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
+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
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.
0

go to edit and convert it.

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

1
2