Are there languages $L_1$, $L_2$ such that such that $$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$ and two other languages such that $$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$ And if so, what are they? How can i go about finding these?
Asked
Active
Viewed 55 times
0
-
what is the $m$? I think the http://cs.stackexchange.com/ is more appropriate for your question – M a m a D Jun 09 '19 at 20:45
-
@Noone the m is for mapping reductions, thanks ill ask there. – Karlberg Jun 09 '19 at 21:34
-
$L_1=L_2=\emptyset$ should work, right? – eepperly16 Jun 09 '19 at 21:39
-
Or any $L_1=L_2$ for that matter – eepperly16 Jun 09 '19 at 21:40
-
My bad, it should be $$L_1 \cup L_2\leq_m, L_1\cap L_2,$$ not $$L_1 \cup L_2\leq_m, L_2\cap L_2,$$ but i like your solution, any solution for the edited one? – Karlberg Jun 10 '19 at 16:51
-
$L_1 = L_2$ is a solution to both the current problems (for any language $L_1$). – John Hughes Jun 10 '19 at 16:53
-
Actually you must look for a computable function $f$, such that $\forall w \in L_1 \cup L_2 \Leftrightarrow f(w) \in L_1 \cap L_2$, not for two languages. Have you ever tried to design any decidable Turing Machine to do this? – M a m a D Jun 11 '19 at 07:19