1
$\begingroup$

If the same $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ does it imply that $L_1=L_2$?

My intuition says no, but I couldn't find a counterexample.

$\endgroup$
1
  • $\begingroup$ Hint: There is a very concise way to express $L_1$ using $f$ and $L$. The same for $L_2$. Check the definition of reduction. $\endgroup$ – user114966 Mar 22 at 2:45
1
$\begingroup$

Using the definition of reduction,

$x\in L_1\iff f(x)\in L \iff x\in L_2$

And thus $L_1=L_2$.

$\endgroup$
-2
$\begingroup$

When a reduction takes place that means that the problem $L_i$ is just a different "point of view" of problem $L$. Given that you have two problems $L_1$ and $L_2$ reducible to the same $L$ then you could say that by solving $L$ you would be able to solve both. This in turn implies that they could be treated as the same problem.

$\endgroup$
2
  • 1
    $\begingroup$ This is not true. Every language in Exp has a reduction to some very hard problem in Exp,, but there are languages that require a poly time turing machine and others that require an exponential time turing machine. Obviously, they are not the same. $\endgroup$ – nir shahar Mar 22 at 6:34
  • $\begingroup$ The OP however asked what would happen if the reduction function is the same. Its a bit different in this case. $\endgroup$ – nir shahar Mar 22 at 6:36

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.