two languages reducible to each other can belong to RE and recursive?

Question

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

C both

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?

Answer 1

Reductions are translations between computational problems. Reductions are used to define the concept of NP-hardness but that doesn't mean that every use of reductions has something to do with NP – analogously, you can translate between English and French but that doesn't mean that every piece of translation has something to do with French. In this case, there's no reason to assume that we're in the context of P vs NP: the question is in the context of computability theory (what functions can we compute?) not complexity theory (how much resources are required?).

For your question at the end, remember that every decidable language is semi-decidable.

I've no idea what the answer to the multi-choice question is, since it's so badly worded. Choosing "C", for example, would mean asserting that the statement "both" is false but "both" isn't a statement with a truth value.