[Solved]: Does two languages being in P imply reduction to each other?

Problem Detail: Given two languages $L_1$ and $L_2$ that are in $mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the empty language, and $L_2$ is the “full language” ${ 0,1 }^*$, there does not seem to be a reduction from $L_2$ to $L_1$, but this is not clear to me. I know how a reduction works, so that is not a problem for me.

Asked By : Yechiel Labunskiy

Answered By : ymbirtt

Yes

Though you may find the argument to be a bit unsatisfying and fudgy. Recall the definition. $L_1$ reduces to $L_2$ iff there exists a function $f: Sigma^* rightarrow Sigma^*$ such that $forall w in L_1, f(w) in L_2$, and $forall w notin L_1, f(w) notin L_2$, and $f$ is computable in polynomial time. Both $L_1$ and $L_2$ are in $P$, so we can decide them in polynomial time. We’ll ignore the trivial edge cases where $L_1$ or $L_2$ are either empty or contain everything. Let $w_top in L_2$ and $w_bot notin L_2$. These words are constant, so are of constant length. We will define $f$ as follows. If $w in L_1$, then $f(w)=w_top$. If $w notin L_1$, then $f(w)=w_bot$. Clearly, $f$ represents a reduction from $L_1$ to $L_2$ according to the above definition. Since $L_1$ can be decided in polynomial time, we can compute $f$ in polynomial time. So $f$ is a poly-time reduction from $L_1$ to $L_2$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19427