Dark Mode

14,161 views

57 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?

- If $A\: \leq_m B$ and $B$ is recursive then $A$ is recursive.
- If $A\: \leq_m B$ and $A$ is undecidable then $B$ is undecidable.
- If $A\: \leq_m B$ and $B$ is recursively enumerable then $A$ is recursively enumerable.
- If $A\: \leq_m B$ and $B$ is not recursively enumerable then $A$ is not recursively enumerable.

edited
Nov 19, 2021
by ankit3009

I am not able to clearly understand what we actually mean by reducing, please help.

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.

few more contents: https://gateoverflow.in/39721/Gate-cse-2016-set-1-question-44?show=330343#a330343

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

0

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

0

50 votes

Best answer

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

0

43 votes

3 votes

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

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

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