Problem Detail: Throughout the subject of reductions, I was wondering:
If we take $L_1 = Sigma^* $ and $L_2 = emptyset$, is $L_1 leq L_2$? is $L_2 leq L_1$?
What I mean is, Is there some sort of reduction between any of the two with the other one? I tried this:
Let us try $L_2 leq L_1$, we need to show that such a reduction exists. Suppose f(x) is that reduction function in which $x in L_2$ iff $f(x) in L_1$.
But there aren’t any $x$ in $emptyset = L_2$, does that show that such a reduction doesn’t exist?
Asked By : TheNotMe
Answered By : Raphael
Let $f : Sigma^* to Sigma^*$ any total function. Then, the statement $x in L_2$ is always false since $L_2 = emptyset$, and conversely $f(x) in L_1$ is always true since $L_1 = Sigma^*$. So, clearly, the equivalence $qquaddisplaystyle x in L_2 iff f(x) in L_1$ is false for $f$ and all $x in Sigma^*$ (it would have been sufficient to find one example-$x$); in fact, $qquaddisplaystyle x in L_2 iff f(x) notin L_1$ holds for all $x$. So $f$ is not a reduction function. Since we picked $f$ arbitrarily, there can be no reduction from $L_2$ to $L_1$. A similar argument works for the other direction.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19599
