5
$\begingroup$

How would I go about showing that L $\leq_p$ L' does not necessarily imply L' $\leq_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other way round, but am not sure what such problems could be.

$\endgroup$
4
$\begingroup$

You have a good plan of approach. Now you need to spend some more time pursuing this. Try to come up with a list of languages $L$ you've seen before, and try different pairs to see if they satisfy the condition. After some trial and error you should be able to solve your problem.

$\endgroup$
2
  • $\begingroup$ I was thinking something like SAT < HALT but not the other way round? $\endgroup$ – gallifreyfields May 31 '16 at 10:23
  • $\begingroup$ @JasmineGrosso, don't just guess -- try to prove your answer correct! That's how you will know whether you are right or not. $\endgroup$ – D.W. May 31 '16 at 15:47
4
$\begingroup$

Maybe this insight will be helpful (along with your own thoughts and D.W.'s answer):

Quite intuitively, the relation $A \le_p B$ indicates that $B$ is more "difficult" than $A$. Indeed, for an NP-hard problem, like SAT, we know that all other NP languages $A$ can be reduced to it, which makes it "the hardest".. But not all languages are NP-hard, some languages are "easier" than others..

$\endgroup$
1
  • $\begingroup$ I would go with a trivial set for A, no need to complicate things with bringing in SAT. ;) $\endgroup$ – Kaveh Jun 19 '16 at 11:59

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.