1
$\begingroup$

This is an old exam question, but I never found a solution or somebody who could explain it to me. Here is the problem statement:

Let $\Sigma$ be an alphabet with |$\Sigma$| $\geq 2$. Show that for any Languages $L_1 \subseteq \Sigma^*$ and $L_2 \subseteq \Sigma^*$ there is a Language $L \subseteq \Sigma^*$ and the following holds true: $L_1 \leq_{log} L$ and $L_2 \leq_{log} L$.

So $L_1$ and $L_2$ are both logspace reducible to $L$

This question gives just 5 out of 60 points for the correct answer, so I assume it shouldn't be too hard to solve. But I don't have any idea on how to approach this problem...

Thank you!

$\endgroup$

1 Answer 1

1
$\begingroup$

Just take $L = \{ 0x \mid x \in L_1 \} \cup \{ 1y \mid y \in L_2\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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