Decidability

Question

Let A, B, C and D are problems. Consider the following polynomial reductions to known about the problem B. 
(i) AB (A is reducible to B) 
(ii) C D 
(iii) B D 
Find the correct statement from the following

1.. if A is decidable, B is decidable

2. if D is undecidable, B is undecidable

3. if C is decidable, B is decidable

4. if A is undecidable, B is undecidable

Comments

pls explain how

---

Agreed with @shubham and @abhinav as 4th one is standard theorem...

---

https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lectures/Lec9-Reducibility.pdf

above 30th slide all explanation is there,

A≤B and B is decidable then A is decidable.
A≤B and A is undecidable then B is undecidable.

A≤B and B is recursively enumerable then A is recursively enumerable.
A≤B and A is not recursively enumerable then B is also not recursively enumerable.

 

Answer 1

CORRECT ANSWER: ( D )

We can easily represent conditions (i), (ii) and (iii) using below diagram :

Now we can check each option one by one,

OPTION - A : A is reducible to B and B belongs to greater set than that of A. It implies there can be some strings in language B that are not in A, which may or may not be decidable. Hence, it is not necessary that B is decidable if A is decidable.

OPTION - B : B is reducible to D and B belongs to smaller set than that of D. It implies B can have all the strings that are decidable. Hence, it is not necessary that  B is undecidable if D is undecidable.

OPTION - C : Since, B and C can be entirely different set. Hence, it is not necessary that B is decidable if C is decidable.

OPTION - D : Since A is reducible to B and B is reducible to D implies A is reducible to D. Now, A <= D, means if A is undecidable whole D becomes undecidable. Hence, it is necessary that D is undecidable if A is undecidable.

Correct Answer is ( D ).