426 views

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?

1.  L1 is decidable and L2 is undecidable.
2.  L1 is regular and L2 is CFL.
3.  L1 is recursive and L2 is recursively enumerable.
4.  L1 is decidable and L2 is decidable.

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

1
577 views