14,161 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.

beautiful question…...
edited

I formed some relations and came to a conclusion that,

Going by definition, it can be “A cannot be harder to solve than solving B” OR

“A ≤ B :  it means that solution of problem B can be used to solve problem A.”

Say, for eg. if B is CSL, then for A is reducible to B, A will be at max CSL or it may be RL, CFL (according to Chomsky hierarchy).

Similarly, if B is recursive, then as A can’t be harder than recursive, so it can be either recursive or CSL, CFL, RL.

Similarly, if B is NOT RE, then as A can’t be harder than NOT RE, so it can be either not RE, RE, RE but not rec, recursive , CSL, CFL, RL.

Also, it depends on whether you are given A and asked to find B or vice versa. Like if A is reducible to B, then say if you are given A is NOT RE then we can be sure that B is NOT RE. But if we are given B is NOT RE then we can’t be sure that A is not RE.

Please let me know if my approach or any of the examples I took is wrong.

A → B (A is reducible to B) it means ‘A’ can’t be more harder than B (means if ‘B’ is hard then ‘A’ can be easy or equal hard to ‘B’).

(a) A → B here if ‘B’ is recursive then ‘A’ can be recursive (equal hard to ‘B’) or ‘A’ can be reg, CFL, CSL (easy than ‘B’) and if ‘A’ is reg, CFL, CSL then ultimately it is recursive (bcoz every CSL is recursive) therefore (a) is true.

(b) A → B here if ‘A’ is undecidable then ‘B’ can be undecidable (but ‘B’ can’t be decidable if so i.e. if ‘B’ is decidable and ‘A; is undecidable means ‘A’ become harder than ‘B’ which is not possible if A → B) therefor (b) is true.

( c) A → B here if ‘B’ is REL then ‘A’ can be REL (equal hard to ‘B’) or ‘A’ can be rec, reg, CFL, CSL (easy than ‘B’) and if ‘A’ is reg, CFL, CSL, recursive then ultimately it is REL (bcoz every recursive lang is REL) therefore (c) is true.

(d) A → B here if ‘B’ is not REL then ‘A’ can be not REL (equal hard to ‘B’) or ‘A’ can be REL (easy than ‘B’) now contradiction arises therefore (d) is not possible (d) is false.

is this right approach to solve such questions? please correct me if I am wrong..

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

by

thanx bro @ravee_rocks
why is option C wrong ?

@Rutuja Desai Option C is TRUE. Q is asking which statement is false.

Nevertheless, in Option C) $A\: \leq_m B$, if B is RE (means semi-decidable) then, A is also RE (semi decidable) is TRUE.

This slide explains everything

Note: The last two points are the contrapositive of the first two respectively.
It just states , it doesn't explains
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 comment

Some more:

$1)$ If B is D then A is D

$2)$ If A is not Recursive then B is not Recursive

$3)$ If A is D then B may or may not D

$4)$ if B is UD then A may or may not UD
• 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

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

go to edit and convert it.