patternModerate
Does two languages being in P imply reduction to each other?
Viewed 0 times
implyeachlanguagesbeingtworeductiondoesother
Problem
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.
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.
Solution
No, in general
As you've already noticed, if $L_2$ is either the full language or the empty language, there can be no reduction from $L_1$ to $L_2$ - the argument is simple enough.
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.
Suppose $L_1 \neq \emptyset$ and $L_2 = \emptyset$. Suppose also that some function $f$ exists such that $w \in L_1 \implies f(w) \in L_2$. This argument immediately gives us a contradiction. We know that $w \in L_1$ can be true, but $f(w) \in \emptyset$ can never be true, so there cannot be such an $f$, poly-time or not.
The argument for $L_1\neq\Sigma^{}$ and $L_2 = \Sigma^{}$ is similar. For any function $f: \Sigma^ \rightarrow \Sigma^$, $w \in L_1$ can be false, but $f(w) \in \Sigma^{*}$ is always true.
There are some other subtleties floating around this question, and it's a worthwhile exercise to think of all the possible combinations you could get from assigning $L_1$ and $L_2$ to $\emptyset$, $\Sigma^{*}$ and some non-empty non-"full" language.
This said, with a further assumption, there's a small trick we can apply to make this argument hold:
Yes, if we have that neither $L_1$ nor $L_2$ are empty or "full"
Both $L_1$ and $L_2$ are in $P$, so we can decide them in polynomial time.
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$. This argument can work the other way to provide a reduction from $L_2$ to $L_1$, so the languages reduce to each other.
If exactly one of $L_1$ or $L_2$ is empty or "full", we can reduce from one to the other. Which way? Why?
As you've already noticed, if $L_2$ is either the full language or the empty language, there can be no reduction from $L_1$ to $L_2$ - the argument is simple enough.
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.
Suppose $L_1 \neq \emptyset$ and $L_2 = \emptyset$. Suppose also that some function $f$ exists such that $w \in L_1 \implies f(w) \in L_2$. This argument immediately gives us a contradiction. We know that $w \in L_1$ can be true, but $f(w) \in \emptyset$ can never be true, so there cannot be such an $f$, poly-time or not.
The argument for $L_1\neq\Sigma^{}$ and $L_2 = \Sigma^{}$ is similar. For any function $f: \Sigma^ \rightarrow \Sigma^$, $w \in L_1$ can be false, but $f(w) \in \Sigma^{*}$ is always true.
There are some other subtleties floating around this question, and it's a worthwhile exercise to think of all the possible combinations you could get from assigning $L_1$ and $L_2$ to $\emptyset$, $\Sigma^{*}$ and some non-empty non-"full" language.
This said, with a further assumption, there's a small trick we can apply to make this argument hold:
Yes, if we have that neither $L_1$ nor $L_2$ are empty or "full"
Both $L_1$ and $L_2$ are in $P$, so we can decide them in polynomial time.
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$. This argument can work the other way to provide a reduction from $L_2$ to $L_1$, so the languages reduce to each other.
If exactly one of $L_1$ or $L_2$ is empty or "full", we can reduce from one to the other. Which way? Why?
Context
StackExchange Computer Science Q#19427, answer score: 11
Revisions (0)
No revisions yet.