[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