# Does two languages being in P imply reduction to each other?

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.

• That's actually an interesting edge case that I hadn't spotted, but usually for these sorts of problems we ignore these edge cases $\emptyset$ and $\Sigma^*$. Can you recall the definition of a reduction? – ymbirtt Dec 31 '13 at 22:37
• L1 <= L2 if there exists a reduction function f such that for all input X, X is part of L1 IFF f(X) is part of L2. – Yechiel Labunskiy Dec 31 '13 at 22:40
• See here. Also, brushing up on fundamentals might help. – Raphael Jan 3 '14 at 14:05

# 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_2 = \Sigma^{*}$ is similar.

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?

• Thanks for your help, a bit fudgy in my mind, but starting to sink in. – Yechiel Labunskiy Dec 31 '13 at 22:55
• ymbirtt, Normally we try not to just dump the complete answer to a question that looks like a homework exercise, especially when the question shows no evidence of effort. (It might be what the original author is hoping for, but I don't think it's doing them a service, and I don't think it's good for our community in the long run -- it just encourages more such bad questions.) I tend to think it is better to provide hints, or better still, wait for the original author to make a serious effort on their own and come back to show us what they've tried. – D.W. Dec 31 '13 at 22:59
• $\Sigma^*$ and $\emptyset$ are valid languages in $P$. They are not trivial cases. So the answer is actually NO. This answer needs to be edited to be more complete. – Auberon Feb 20 '17 at 15:48
• @Auberon, yep, you're right! Damn, I was sloppy 3 years ago, wasn't I? I'll throw an updated version together momentarily. – ymbirtt Feb 21 '17 at 8:27
• "No in general" is a rather misleading way of saying "Yes, except in two special cases." – David Richerby Feb 21 '17 at 9:17