# 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