If two languages L1 and L2 both are reducible to each other in polynomial time then which of the following is false?
A L1 is decidable and L2 is undecidable.
B L1 is recursive and l2 is RE
D none of these
I know that both need to belong to NP or NP hard if they are reducible to each other. simply solving one solves other.
If L1 is recursive then L2 also needs to be recursive. in context of P-NP if L1 is decidable and by doing extra polynomial work i can get Turing machine for L2 as well ans vice versa . why one is decidable and other is semi-decidable a true statement?