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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.