1
$\begingroup$

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

enter image description here

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What is this image doing there? You should give attribution by naming the author and source, not by posting screenshots. $\endgroup$ – Raphael♦ Jan 20 '16 at 11:13
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.