Test by Bikram | Theory of Computation | Test 1 | Question: 5

Question

If a language L1 is polynomially reduced to the language L2 and L2 is polynomially reduced to the language L1, then which of the following cannot be TRUE?

• A.  L1 is decidable and L2 is undecidable.  
• B.  L1 is regular and L2 is CFL.
• C.  L1 is recursive and L2 is recursively enumerable.
• D.  L1 is decidable and L2 is decidable.

Comments

In one of the above comments it is mentioned--

L2 recursive and L1 r.e. is possible when both are recursive as a recursive language is also a r.e. language.

I don't know rest :/

Option b may be true if both L1 and L2 are regular languages.

---

hmmm!

---

Can someone explain why B and C are true?

I just learnt that

1. If A is reducible to B and B is Recursive language then A is also Recursive language. 
2. If A is reducible to B and B is Recursive Enumerable language then A is also Recursive Enumerable language.
3. If A is reducible to B and A is not Recursive Enumerable language then B is also not Recursive Enumerable language.

But I don’t know the actual logic behind it and I also don't know that If P is polynomially reducible to Q then If P is Regular implies Q has to Regular or not?

If someone can explain the logic or just share some reference then it will be very helpful