in Theory of Computation edited by
14,161 views
57 votes
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?

  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.
in Theory of Computation edited by
14.2k views

4 Comments

beautiful question…...
0
0
edited by

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

4 Answers

50 votes
50 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. 

edited by
by

4 Comments

thanx bro @ravee_rocks
0
0
why is option C wrong ?
0
0

@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
0
43 votes
43 votes

This slide explains everything

4 Comments

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

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
1
1
0 votes
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

4 Comments

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?
1
1
I also think so c is the answer
0
0
moved by
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
0

@Shubham Aggarwal 

convert your answer to comment.

go to edit and convert it.

0
0
Answer:

Related questions