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